(라이님 블로그 대회 알고리즘 따라잡기 31) KMP(Knuth–Morris–Pratt Algorithm)

오늘은 KMP 알고리즘에 대해 공부해보았다. 솔직히 개념 + 코드 이해하는데 좀 걸렸다...

뭔가 직관적이지 않아서 이해가 단번에 되지 않았다..ㅠ

 

늘 그렇듯 설명은 라이님 블로그에 있다.(아휴 어려워)

 

그래도 보다보니 이해가 되는거 같기도 하다...^^

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string S, W;
    getline(cin, S);
    getline(cin, W);

    int N = S.length();
    int M = W.length();

    // Fail function computation directly in main
    vector<int> fail(M, 0);  // 0으로 초기화된 벡터 생성
    for (int i = 1, j = 0; i < M; i++) {
        while (j > 0 && W[i] != W[j]) j = fail[j - 1];
        if (W[i] == W[j]) {
            fail[i] = ++j;
        }
    }

    // KMP algorithm
    vector<int> result;
    for (int i = 0, j = 0; i < N; i++) {
        while (j > 0 && S[i] != W[j]) j = fail[j - 1];
        if (S[i] == W[j]) {
            if (j == M - 1) {
                result.push_back(i - M + 2); // +1 for 1-based index
                j = fail[j];
            }
            else {
                j++;
            }
        }
    }

    cout << result.size() << endl;
    for (int i : result) cout << i << " ";
    cout << endl;

    return 0;
}