SyntaxPilot
Courses/Competitive Programming/Lesson 72
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 72 of 90

KMP and prefix-function problems

queued

These are the notes for Competitive Programming episode 72. The prefix function π[i] is the length of the longest border (a proper prefix that is also a suffix) of s[0..i]. It is computed in O(n) by falling back from a border to the next shorter one (j = π[j − 1]), and it is the heart of the Knuth–Morris–Pratt (KMP) algorithm. Signal Search (count the occurrences of p in t) shows the try-every-start brute force (TLE), and matching with π of p + '#' + t, including a real bug: without the separator, aa in aaaa gives 1 instead of 3. Banner Tiles (the shortest repeating tile) is one line: n − π[n − 1]. Unlike hashing, everything here is exact. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A keypad door lock has the code 1 2 1 3. You type 1 2 1 2: the fourth key is wrong. A simple lock forgets everything and waits for the code from the start. A smart lock notices that the last two keys, 1 2, are the start of the code, keeps them, and waits for a 1. If even that fails, it tries the next shorter start that still fits. Every key is read once. That memory, "how much of what I've seen ends with a start of the code", is the prefix function.

(Written for this course.)

  • A text t (a radio log) and a pattern p (a call sign), lowercase letters, |t|, |p| ≤ 10^6.
  • Print the number of positions where p occurs in t (overlapping occurrences count).
aba
abababa

aba occurs in abababa at positions 1, 3 and 5: 3.

Attempt 1: try every start (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(const string& p, const string& t) {   // try every start
    int n = t.size(), m = p.size(), cnt = 0;
    for (int s = 0; s + m <= n; s++) {
        int k = 0;
        while (k < m && t[s + k] == p[k]) k++;
        if (k == m) cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string p, t;
    cin >> p >> t;
    cout << brute(p, t) << "\n";
}
3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(const string& p, const string& t) {   // try every start
    int n = t.size(), m = p.size(), cnt = 0;
    for (int s = 0; s + m <= n; s++) {
        int k = 0;
        while (k < m && t[s + k] == p[k]) k++;
        if (k == m) cnt++;
    }
    return cnt;
}

int main() {
    string t(1000000, 'a'), p(500000, 'a');      // the worst case
    cout << brute(p, t) << "\n";
}
Time Limit Exceeded

Half a million starts, each comparing half a million letters: it forgets what it has read after every start.

Borders and the prefix function

  • A border of a string is a proper prefix that is also a suffix: abacaba has borders a and aba.
  • π[i] = the length of the longest border of s[0..i].
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    string s;
    cin >> s;
    for (int x : prefix_function(s)) cout << x << " ";
}
abacaba
0 0 1 0 1 2 3

Computing π in O(n)

  • j = π[i − 1]: try to extend the best border of the previous prefix by one letter.
  • while (j > 0 && s[i] != s[j]) j = π[j − 1]: fall back to the next shorter border (a border of a border is a border).
  • if s[i] == s[j], j++; π[i] = j.
  • j grows by at most 1 per position and every fall back decreases it, so all the fall backs together are at most n: O(n).

Matching with π: the missing separator

If p is glued in front of t, a border of length |p| ending inside t means p ends right there. First without a separator:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int kmp(const string& p, const string& t) {
    int m = p.size(), cnt = 0;
    vector<int> pi = prefix_function(p + t);
    for (int x : pi) if (x == m) cnt++;           // a border as long as p = a match
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string p, t;
    cin >> p >> t;
    cout << kmp(p, t) << "\n";
}

Sample, then the edge case aa / aaaa:

3
1

Wrong Answer (the brute force says 3). aaaaaa has π = 0 1 2 3 4 5: borders run through p into t and grow longer than p, so π equals 2 only once, inside p itself.

The fix: p + '#' + t

A character that appears in neither string stops every border at length |p|.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int kmp(const string& p, const string& t) {
    int m = p.size(), cnt = 0;
    vector<int> pi = prefix_function(p + '#' + t);
    for (int x : pi) if (x == m) cnt++;           // a border as long as p = a match
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string p, t;
    cin >> p >> t;
    cout << kmp(p, t) << "\n";
}
3
3

A pattern longer than the text (abcd / abc):

0

The worst case that killed the brute force:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int kmp(const string& p, const string& t) {
    int m = p.size(), cnt = 0;
    vector<int> pi = prefix_function(p + '#' + t);
    for (int x : pi) if (x == m) cnt++;           // a border as long as p = a match
    return cnt;
}

int main() {
    string t(1000000, 'a'), p(500000, 'a');      // the worst case
    cout << kmp(p, t) << "\n";
}
500001
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int brute(const string& p, const string& t) {   // try every start
    int n = t.size(), m = p.size(), cnt = 0;
    for (int s = 0; s + m <= n; s++) {
        int k = 0;
        while (k < m && t[s + k] == p[k]) k++;
        if (k == m) cnt++;
    }
    return cnt;
}

int kmp(const string& p, const string& t) {
    int m = p.size(), cnt = 0;
    vector<int> pi = prefix_function(p + '#' + t);
    for (int x : pi) if (x == m) cnt++;           // a border as long as p = a match
    return cnt;
}

int main() {
    mt19937 gen(72);
    for (int t = 1; t <= 500; t++) {
        string p(gen() % 4 + 1, 'a'), s(gen() % 15 + 1, 'a');
        for (char& c : p) c = 'a' + gen() % 2;
        for (char& c : s) c = 'a' + gen() % 2;
        if (brute(p, s) != kmp(p, s)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem R2 · Banner Tiles

(Written for this course.)

  • A banner s (|s| ≤ 10^6) was printed by repeating one tile; the last copy may be cut off.
  • Print the length of the shortest possible tile, and exact if it repeats a whole number of times, else cut.

abcabcab → 3 cut (tile abc) · abab → 2 exact · a → 1 exact.

The observation

  • A border of length b means s shifted by n − b lines up with itself: s[i] = s[i − (n − b)] for every i, so n − b is a period.
  • The longest border gives the shortest period: n − π[n − 1]. It is exact iff n is divisible by it.

Attempt 1: try every tile length (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    for (int p = 1; p <= n; p++) {                 // try every tile length
        bool ok = true;
        for (int i = p; i < n && ok; i++)
            if (s[i] != s[i - p]) ok = false;
        if (ok) {
            cout << p << (n % p == 0 ? " exact" : " cut") << "\n";
            break;
        }
    }
}
3 cut

aaaa…ab (a million letters): every tile length matches almost to the end.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000;
    string s(n, 'a');
    s[n - 1] = 'b';                              // aaaa...ab
    for (int p = 1; p <= n; p++) {                 // try every tile length
        bool ok = true;
        for (int i = p; i < n && ok; i++)
            if (s[i] != s[i - p]) ok = false;
        if (ok) {
            cout << p << (n % p == 0 ? " exact" : " cut") << "\n";
            break;
        }
    }
}
Time Limit Exceeded

With the prefix function

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> pi = prefix_function(s);
    int p = n - pi[n - 1];                         // the shortest period
    cout << p << (n % p == 0 ? " exact" : " cut") << "\n";
}
3 cut
2 exact
1 exact
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    int n = 1000000;
    string s(n, 'a');
    s[n - 1] = 'b';                              // aaaa...ab
    vector<int> pi = prefix_function(s);
    int p = n - pi[n - 1];                         // the shortest period
    cout << p << (n % p == 0 ? " exact" : " cut") << "\n";
}
1000000 exact
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int slow(const string& s) {
    int n = s.size();
    for (int p = 1; p <= n; p++) {
        bool ok = true;
        for (int i = p; i < n; i++) if (s[i] != s[i - p]) ok = false;
        if (ok) return p;
    }
    return n;
}

int main() {
    mt19937 gen(72);
    for (int t = 1; t <= 500; t++) {
        string s(gen() % 12 + 1, 'a');
        for (char& c : s) c = 'a' + gen() % 2;
        if (slow(s) != (int)s.size() - prefix_function(s).back()) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict
R1: try every start O( t
R1: π of p + '#' + t O( t
R2: try every tile O(n²) ≈ 5·10^11 TLE
R2: n − π[n − 1] O(n) accepted
hashing (episode 71) O(n) tiny chance of error

Memory: one int array of |p| + |t| + 1. The classic KMP matcher stores π of p only and streams t, using O(|p|) memory.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
prefix_function(p + t) 1 instead of 3 on aa / aaaa borders cross from p into t p + '#' + t
if instead of while when falling back Wrong Answer (aaab: π = 0 1 2 1 instead of 0 1 2 0) one step back may still mismatch while (j > 0 && s[i] != s[j])
j = pi[j] instead of pi[j − 1] Wrong Answer or a loop the border of the first j letters is at index j − 1 j = pi[j - 1]
j = 0 on a mismatch misses overlapping matches forgets a shorter border fall back through π
separator that occurs in the strings Wrong Answer borders can cross it a character outside the alphabet
period without the divisibility check abcab reported as exact n − π[n−1] can leave a cut copy check n % p == 0

Mini project

Write a streaming matcher: compute π of the pattern only, then read the text one character at a time from cin and print every match position, using O(|p|) memory. Test it against the p + '#' + t version.

Practice

These are the homework problems from the episode.

1. Print every match position. A match ends at index i of p#t when π[i] = m; it starts in t (1-indexed) at i − 2m + 1.

2. How often does each prefix of s occur in s? Count cnt[π[i]]++, then pass counts to shorter borders from long to short (cnt[π[len − 1]] += cnt[len]), and add 1 for the prefix itself.

Solutions for 1 and 2 (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s) {
    int n = 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;
}

int main() {                                        // every match position (1-indexed)
    string p, t;
    cin >> p >> t;
    int m = p.size();
    vector<int> pi = prefix_function(p + '#' + t);
    for (int i = 0; i < (int)pi.size(); i++)
        if (pi[i] == m) cout << i - 2 * m + 1 << " ";   // match ends at index i of p#t
    cout << "\n";
}
aba
abababa
1 3 5
#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s) {
    int n = 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;
}

int main() {                                        // how often each prefix occurs in s
    string s;
    cin >> s;
    int n = s.size();
    vector<int> pi = prefix_function(s), cnt(n + 1, 0);
    for (int i = 0; i < n; i++) cnt[pi[i]]++;       // the longest border ending at i
    for (int len = n; len > 0; len--) cnt[pi[len - 1]] += cnt[len];   // pass to shorter borders
    for (int len = 1; len <= n; len++) cout << cnt[len] + 1 << " ";   // + the prefix itself
    cout << "\n";
}
abacaba
4 2 2 1 1 1 1

3. Shortest string to append to make s a palindrome. Let r = reverse(s). The longest suffix of s that is a palindrome has length π of r + '#' + s at the last position; append the reverse of the remaining prefix.

Hint

For abac: the longest palindromic suffix is c, so append the reverse of aba, giving abacaba.

4. Smallest period of every prefix. For the prefix of length m it's m − π[m − 1]: one pass, O(n).

Hint

Print i + 1 - pi[i] for every i.

Quick quiz

s = "aabaaab"
// pi[i] = longest proper prefix of s[0..i]
//         that is also its suffix

A) 0 1 0 1 2 2 3 · B) 0 1 0 1 2 3 4 · C) 0 1 0 0 1 2 3 · D) 0 0 0 1 2 2 3

Answer

A. At index 5 the border aa needs a b next; fall back to a, which grows into aa → 2. Then aa + b = aab → 3.

Interview questions

  1. What is the prefix function? π[i] is the length of the longest proper prefix of s[0..i] that is also its suffix.
  2. Why is computing it O(n)? j increases by at most 1 per step and each fall back decreases it, so the total number of fall backs is at most n.
  3. How does KMP find a pattern? Compute π of p + separator + t and report positions where π equals |p| (or stream t against π of p).
  4. Why the separator? Without it, borders can extend from p into t and become longer than p.
  5. How do you find the shortest period? n − π[n − 1]; the string is a whole number of copies iff n is divisible by it.
  6. KMP vs hashing? Both are linear; KMP is deterministic and exact, hashing is simpler for comparing arbitrary substrings but can collide.
  7. What is a failure function? Another name for the prefix function in the KMP automaton.

Glossary

Term Meaning Example
Pattern matching Finding where a pattern occurs in a text aba in abababa
Brute force matching Comparing at every start TLE on aaaa…
Border A proper prefix that is also a suffix aba in abacaba
Proper prefix A prefix shorter than the whole string abacab
Prefix function π Longest border of every prefix 0 0 1 0 1 2 3
Fall back Moving to the next shorter border, j = π[j − 1] the smart lock
KMP (Knuth–Morris–Pratt) Linear-time matching using π p + '#' + t
Failure function KMP's name for π —
Separator A character in neither string, between p and t #
Overlapping occurrences Matches that share letters aba at 1 and 3
Period p such that s[i] = s[i − p] for all valid i 3 for abcabcab
Exact period A period that divides the length 2 for abab
Amortised O(n) Total work bounded over the whole run the fall backs
Stress test Fast vs brute force on many random inputs all 500 tests passed
Z-function For each i, the longest match of s[i..] with s's start next episode

Summary

  • π[i] = the longest border of s[0..i]; compute it in O(n) by falling back with j = π[j − 1] in a while loop.
  • Matching: π of p + '#' + t, count π = |p|. Without the separator, borders cross into t.
  • Shortest period: n − π[n − 1]; exact iff it divides n.
  • KMP is linear and exact, unlike hashing.

Solutions in C++, Java and Python

Problem R1 · Signal Search

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int kmp(const string& p, const string& t) {
    int m = p.size(), cnt = 0;
    vector<int> pi = prefix_function(p + '#' + t);
    for (int x : pi) if (x == m) cnt++;           // a border as long as p = a match
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string p, t;
    cin >> p >> t;
    cout << kmp(p, t) << "\n";
}

Java (checked on the samples and 10 random tests against the C++ brute force)

import java.io.*;

public class Main {
    static int[] prefixFunction(byte[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];                             // the best border so far
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String p = br.readLine().trim(), t = br.readLine().trim();
        byte[] s = (p + "#" + t).getBytes();
        int m = p.length(), cnt = 0;
        for (int x : prefixFunction(s)) if (x == m) cnt++;
        System.out.println(cnt);
    }
}

Python

import sys

def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]                       # the best border so far
        while j > 0 and s[i] != s[j]:       # fall back
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

p, t = sys.stdin.read().split()
m = len(p)
print(sum(1 for x in prefix_function(p + "#" + t) if x == m))

Problem R2 · Banner Tiles

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];                       // the best border so far
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> pi = prefix_function(s);
    int p = n - pi[n - 1];                         // the shortest period
    cout << p << (n % p == 0 ? " exact" : " cut") << "\n";
}

Java

import java.io.*;

public class Main {
    static int[] prefixFunction(byte[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];                             // the best border so far
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // fall back
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        byte[] s = br.readLine().trim().getBytes();
        int n = s.length;
        int[] pi = prefixFunction(s);
        int p = n - pi[n - 1];                             // the shortest period
        System.out.println(p + (n % p == 0 ? " exact" : " cut"));
    }
}

Python

import sys

def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]                       # the best border so far
        while j > 0 and s[i] != s[j]:       # fall back
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

s = sys.stdin.read().split()[0]
n = len(s)
p = n - prefix_function(s)[-1]              # the shortest period
print(p, "exact" if n % p == 0 else "cut")