Prefix function (KMP)
For each position, the longest proper prefix that is also a suffix. It gives pattern search in and the "periods" of a word.
When
Find all occurrences of a pattern, or answer questions about the structure of a word: borders, periods, how many times a prefix repeats.
The idea
is the length of the longest proper prefix of that is also a suffix of it. For , .
The key: if is the matching suffix and , the next smaller candidate length is not but . Any border of shorter than is also a border of . That is why the inner loop does .
grows by at most 1 per step and each iteration of the inner loop decreases it. So the total is .
Search. Build . A position with means an occurrence of ending there. The must not occur in either word, so that no match crosses it.
Borders. The borders of the word are , , … down to 0. The smallest period is .
Pitfalls
- The prefix function and the Z-function solve almost the same problems. Learn one well, and recognise the other when you see it in a solution.
findAllbuilds a new string of length . Under a memory limit this rarely matters, but if it does, run the matching over keeping only the of .
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Prefix function (Knuth–Morris–Pratt).
// pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix of it. O(n).
// findAll: every position where pattern occurs in text, via the string pattern + '#' + text.
// The separator must not appear in either string.
vector<int> prefixFunction(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int k = pi[i - 1];
while (k > 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k++;
}
pi[i] = k;
}
return pi;
}
vector<int> findAll(const string& text, const string& pattern) {
vector<int> result;
int m = pattern.size();
if (m == 0) {
return result;
}
vector<int> pi = prefixFunction(pattern + '#' + text);
for (int i = 2 * m; i < (int)pi.size(); i++) {
if (pi[i] == m) {
result.push_back(i - 2 * m);
}
}
return result;
}
Tested on 3,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- String Matching · String Algorithms
- Finding Borders · String Algorithms
- String Functions · String Algorithms
More in the USACO Guide
- String Searching · usaco.guide/adv/string-search
In English, with more problems per level.