KMP (Knuth Morris Pratt) / Z-Algorithm

kmp.cpp

vector<int> kmp(string S) { // pi[i] = length of longest proper prefix of S[0,i] that's also a suffix (ie: border)
    vector<int> pi(S.size());
    for (int i = 1; i < S.size(); i++) {
        int g = pi[i - 1];
        while (g > 0 && S[i] != S[g])
            g = pi[g - 1];
        pi[i] = g + (S[i] == S[g]);
    }
    return pi;
}
vector<int> match(string S, const string &P) {
    vector<int> pi = kmp(P), res;
    int j = 0;
    for (int i = 0; i < S.size(); i++) {
        while (j > 0 && S[i] != P[j])
            j = pi[j - 1];
        j++;
        if (j == P.size()) {
            res.push_back(i - P.size() + 1);
            j = pi[j - 1];
        }
    }
    return res;
}

Zfunc.cpp

vector<int> Z(string S) { // z[i] = Longest common prefix of S[i:] and S
    vector<int> z(S.size());
    for (int i = 1, l = -1, r = -1; i < S.size(); i++) {
        z[i] = i >= r ? 0 : min(r - i, z[i - l]);
        while (i + z[i] < S.size() && S[i + z[i]] == S[z[i]])
            z[i]++;
        if (i + z[i] > r)
            l = i, r = i + z[i];
    }
    return z;
}