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.
Problem R1 · Signal Search
(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:
abacabahas bordersaandaba. - π[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
exactif it repeats a whole number of times, elsecut.
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
- What is the prefix function? π[i] is the length of the longest proper prefix of s[0..i] that is also its suffix.
- 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.
- How does KMP find a pattern? Compute π of p + separator + t and report positions where π equals |p| (or stream t against π of p).
- Why the separator? Without it, borders can extend from p into t and become longer than p.
- How do you find the shortest period? n − π[n − 1]; the string is a whole number of copies iff n is divisible by it.
- KMP vs hashing? Both are linear; KMP is deterministic and exact, hashing is simpler for comparing arbitrary substrings but can collide.
- 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 withj = π[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")