문자열 - KMP 알고리즘

void getPi(string s, vector<int> &pi) {
    pi.resize(s.size(), 0);
 
    int j = 0;
    for (int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            pi[i] = ++j;
    }
}

 

 

//vector<int> ans에는 부분문자열이 시작하는 인덱스들이 들어간다.
void kmp(string &s, string &p, vector<int> &ans) {
    vector<int> pi;
    getPi(p, pi);
    int j = 0;
    for (int i = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != p[j])
            j = pi[j - 1];
        if (s[i] == p[j]) {
            if (j == p.size() - 1) {          //부분문자열을 찾았음
                ans.push_back(i - p.size() + 1);      //부분 문자열이 시작하는 인덱스를 넣어줌
                j = pi[j];
            }
            else {
                j++;
            }
        }
    }
}