← all categories

Kmp 0b220928

KMP prefix function pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix. findOccurrences(text, pattern) finds every occurrence of pattern in text via pi over pattern + '#' + text (# must not appear in either).

Time: O(n). tested

content/strings/kmp.h

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

vector<int> findOccurrences(string &text, string &pattern) {
    string s = pattern + '#' + text;
    auto pi = prefixFunction(s);
    int m = (int)pattern.size();
    vector<int> res;
    for (int i = m + 1; i < (int)s.size(); i++)
        if (pi[i] == m) res.push_back(i - 2 * m);
    return res;
}