uniolympiads Ελληνικά

Prefix function (KMP)

For each position, the longest proper prefix that is also a suffix. It gives pattern search in O(n+m)O(n + m) 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

πi\pi_i is the length of the longest proper prefix of s0…sis_0 \dots s_i that is also a suffix of it. For s=abacabas = \texttt{abacaba}, π=(0,0,1,0,1,2,3)\pi = (0, 0, 1, 0, 1, 2, 3).

The key: if s0…sk−1s_0 \dots s_{k-1} is the matching suffix and si≠sks_i \ne s_k, the next smaller candidate length is not k−1k - 1 but πk−1\pi_{k-1}. Any border of s0…si−1s_0 \dots s_{i-1} shorter than kk is also a border of s0…sk−1s_0 \dots s_{k-1}. That is why the inner loop does k=πk−1k = \pi_{k-1}.

kk grows by at most 1 per step and each iteration of the inner loop decreases it. So the total is O(n)O(n).

Search. Build p+#+tp + \texttt{\#} + t. A position with πi=∣p∣\pi_i = |p| means an occurrence of pp ending there. The #\texttt{\#} must not occur in either word, so that no match crosses it.

Borders. The borders of the word are πn−1\pi_{n-1}, ππn−1−1\pi_{\pi_{n-1}-1}, … down to 0. The smallest period is n−πn−1n - \pi_{n-1}.

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.
  • findAll builds a new string of length n+m+1n + m + 1. Under a memory limit this rarely matters, but if it does, run the matching over tt keeping only the π\pi of pp.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/kmp.cpp
// 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.

More in the USACO Guide

In English, with more problems per level.