12 String algorithms: KMP, Z and hashing / Lesson 1 of 1

KMP, the Z-function and rolling hashes

16 min · +10 XP · 2 exercises · 4 questions

Read the text16 min

Exercises0/2

Quiz4 q

Quick answer

How does the KMP algorithm work?

The Knuth–Morris–Pratt (KMP) algorithm finds every occurrence of a pattern in a text in O(n + m). It first builds the prefix function: pi[i] is the length of the longest proper prefix of the pattern that is also a suffix of its first i + 1 characters. On a mismatch the match length falls back to pi[j − 1] instead of restarting, so the text pointer never moves backwards.

Searching a pattern of length m in a text of length n by trying every start is O(n · m) — 2.5 × 10⁹ when both are 5 × 10⁴. Three tools do it in O(n + m) by never re-reading what is already known.

The prefix function and KMP

pi[i] = the length of the longest proper prefix of s[0..i] that is also its suffix (its border).
Build it in O(m): try to extend the previous border; on a mismatch fall back to pi[j − 1] and try again.
Match the same way: j characters of the pattern are matched; on a mismatch j = pi[j − 1]; at j = m record a match and fall back to pi[m − 1].
The text index only moves forward, so the whole search is O(n + m).

KMP: build the prefix function, then never move back in the text

pattern = "abab", text = "abababcabab"

pi[i] is the length of the longest proper prefix of the pattern that is also a suffix of its first i + 1 characters. pi[0] is always 0; pi[1] = 0, since "ab" has no border.

0:01 / 0:22Step 1 of 7

Transcript · 7 steps

vector<int> prefixFunction(const string& s) {
    vector<int> pi(s.size(), 0);
    for (size_t i = 1; i < s.size(); ++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;
}

The Z-function

z[i] = the length of the longest common prefix of s and s[i..].
Keep the box [l, r): the rightmost segment known to equal a prefix. Inside it, z[i] starts at min(r − i, z[i − l]) for free; only characters past r are compared.
To find a pattern, run Z on pattern + '#' + text: every z[i] = m is an occurrence.

The Z-function: positions inside the box start from z[i − l]

s = "aabxaabxcaab"

z[i] is how many characters starting at i match the start of s. Comparing from scratch at every i would be O(n²); the box [l, r) of the rightmost match found so far lets most positions start with an answer.

0:01 / 0:38Step 1 of 12

Transcript · 12 steps

Rolling hashes

Prefix hashes h[i+1] = h[i] · B + s[i] (mod p) and powers B^k.
hash(l, r) = h[r] − h[l] · B^(r−l): any substring in O(1), so "are these equal?" is O(1).
One 32-bit modulus collides often enough to fail anti-hash tests; use two moduli with fixed bases (or compare the strings when the hashes agree).
Hashing answers what KMP cannot directly: distinct substrings, the longest repeated substring with binary search, palindromes by comparing with the reversed string.

More practice

Common questions

What is the prefix function in KMP?

For a string s, pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of it. For "abab" it is 0, 0, 1, 2. It is built in O(n) by extending the previous border when the next characters match and falling back through pi otherwise. The last value is the string's longest border.

What is the Z-function?

z[i] is the length of the longest common prefix of the string and its suffix starting at i. The Z algorithm computes it in O(n) by keeping the box [l, r) — the rightmost match found so far — and starting each z[i] inside the box from z[i − l], extending by direct comparison only past r. To find a pattern, compute Z of pattern + '#' + text.

How does a rolling hash compare substrings?

Store prefix hashes h[i] = s[0]·B^(i−1) + … + s[i−1] mod p and the powers of B. The hash of s[l..r) is h[r] − h[l]·B^(r−l) mod p, so any two substrings compare in O(1) after O(n) preparation. Two different moduli make an accidental collision vanishingly unlikely; on a hash hit, an exact comparison removes it entirely.

KMP vs Z-function — which should I use?

Both find all occurrences in O(n + m) and either can answer border and period questions. Use KMP when the pattern is fixed and the text streams past, since it needs only the pattern's table. Use Z when you want, for every position, how far the string matches its own prefix — the concatenation trick makes matching a one-liner.

Mark as readSign in to keep your place.

KMP, Z Algorithm and Rolling Hash in C++ for String Matching

Find every occurrence of a pattern in O(n + m) with the KMP prefix function or the Z-function, and compare substrings in O(1) with a double rolling hash in C++.

Course: Competitive Programming study plan
Module: String algorithms: KMP, Z and hashing
Kind: Lesson
Reading time: 16 min
Runtime: Clang 18 · C++20

How does the KMP algorithm work?

Lesson

The prefix function and KMP

pi[i] = the length of the longest proper prefix of s[0..i] that is also its suffix (its border).
Build it in O(m): try to extend the previous border; on a mismatch fall back to pi[j − 1] and try again.
Match the same way: j characters of the pattern are matched; on a mismatch j = pi[j − 1]; at j = m record a match and fall back to pi[m − 1].
The text index only moves forward, so the whole search is O(n + m).

KMP: build the prefix function, then never move back in the text. Example: pattern = "abab", text = "abababcabab"

pi[i] is the length of the longest proper prefix of the pattern that is also a suffix of its first i + 1 characters. pi[0] is always 0; pi[1] = 0, since "ab" has no border.
"aba": "ab" had no border, so the new a is compared with the first character. They match: pi[2] = 1.
"abab": the previous border "a" extends by b, so pi[3] = 2 — the pattern's longest border is "ab". The table is built in O(m).
Scan the text with j = characters matched. At index 3 all 4 match: an occurrence at index 0.
After the last match j fell back to pi[3] = 2: the pattern slid by 2 and "ab" was already matched, so only 2 new characters were compared. Another match at index 2.
Index 6: text c ≠ pattern a with j = 2. Instead of restarting, j falls back to pi[1] = 0; the text pointer stays at 6.
From j = 0 the pattern is matched afresh, one text character at a time: at index 10 all 4 match, an occurrence at index 7. In all: 3 occurrences, at 0, 2, 7, in one pass of the text.

vector<int> prefixFunction(const string& s) {
    vector<int> pi(s.size(), 0);
    for (size_t i = 1; i < s.size(); ++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;
}

The Z-function

z[i] = the length of the longest common prefix of s and s[i..].
Keep the box [l, r): the rightmost segment known to equal a prefix. Inside it, z[i] starts at min(r − i, z[i − l]) for free; only characters past r are compared.
To find a pattern, run Z on pattern + '#' + text: every z[i] = m is an occurrence.

The Z-function: positions inside the box start from z[i − l]. Example: s = "aabxaabxcaab"

z[i] is how many characters starting at i match the start of s. Comparing from scratch at every i would be O(n²); the box [l, r) of the rightmost match found so far lets most positions start with an answer.
i = 1 is not inside the box: compare from scratch; comparing on gives z[1] = 1. The match reaches past the old box: the box becomes [1, 2).
i = 2 is not inside the box: compare from scratch; s[2] = b differs from s[0], so z[2] = 0.
i = 3 is not inside the box: compare from scratch; s[3] = x differs from s[0], so z[3] = 0.
i = 4 is not inside the box: compare from scratch; comparing on gives z[4] = 4. The match reaches past the old box: the box becomes [4, 8).
i = 5 is inside the box, which copies s from index 0, so z[5] starts at min(r − i, z[1]) = 1 for free; the next character differs, so z[5] = 1.
i = 6 is inside the box, which copies s from index 0, so z[6] starts at min(r − i, z[2]) = 0 for free; the next character differs, so z[6] = 0.
i = 7 is inside the box, which copies s from index 0, so z[7] starts at min(r − i, z[3]) = 0 for free; the next character differs, so z[7] = 0.
i = 8 is not inside the box: compare from scratch; s[8] = c differs from s[0], so z[8] = 0.
i = 9 is not inside the box: compare from scratch; comparing on gives z[9] = 3. The match reaches past the old box: the box becomes [9, 12).
i = 10 is inside the box, which copies s from index 0, so z[10] starts at min(r − i, z[1]) = 1 for free; the next character differs, so z[10] = 1.
i = 11 is inside the box, which copies s from index 0, so z[11] starts at min(r − i, z[2]) = 0 for free; the next character differs, so z[11] = 0.

Rolling hashes

Prefix hashes h[i+1] = h[i] · B + s[i] (mod p) and powers B^k.
hash(l, r) = h[r] − h[l] · B^(r−l): any substring in O(1), so "are these equal?" is O(1).
One 32-bit modulus collides often enough to fail anti-hash tests; use two moduli with fixed bases (or compare the strings when the hashes agree).
Hashing answers what KMP cannot directly: distinct substrings, the longest repeated substring with binary search, palindromes by comparing with the reversed string.

More practice

Common questions

What is the prefix function in KMP?

What is the Z-function?

How does a rolling hash compare substrings?

KMP vs Z-function — which should I use?

Exercises

Every occurrence of a pattern

Read a text t and a pattern p (lowercase letters, one per line). Print the number of positions where p occurs in t — overlapping occurrences count — and, if there is at least one, a second line with the 1-based start positions in increasing order.

Use KMP: build the prefix function of p, then scan t once. O(|t| + |p|).

Constraints: 1 ≤ |t|, |p| ≤ 10^6 (the pattern may be longer than the text). Output: the count, then the positions (no second line when the count is 0).

abababcabab
abab

prints

3
1 3 8

Distinct substrings of each length

Read a string s of lowercase letters, then q lengths. For each length L, print how many distinct substrings of length L the string has.

Hash every window of length L in O(1) with a double rolling hash (two moduli, fixed bases), sort the hashes and count the distinct ones: O(n log n) per query.

Constraints: 1 ≤ |s| ≤ 2 × 10^5, 1 ≤ q ≤ 10, 1 ≤ L ≤ |s|. Input: s, then q, then the q lengths. Output: one count per line.

abab
4
1 2 3 4

prints 2, 2, 2, 1 — {a, b}, {ab, ba}, {aba, bab}, {abab}.

In this module: String algorithms: KMP, Z and hashing

← Checkpoint — DP optimisations · Checkpoint — String algorithms →