KMP (Prefix Function)
O(n)pi[i] is the length of the longest proper prefix of s[0..i] that is also its suffix. To find a pattern in a text, compute the prefix function of pattern + '#' + text: every position where pi equals the pattern length is a match. Also the tool for periods and borders.
// use it on
CSES: String Matching ↗
Count occurrences of a pattern in a text. Run the prefix function on pattern + '#' + text and count positions where pi hits the pattern length.
// the code
// pi[i] = longest proper prefix of s[0..i] that is also a suffix
vector<int> prefix_function(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
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;
}
// matching: auto pi = prefix_function(pat + "#" + text);
// i is a match end when pi[i] == pat.size()