String Algorithms and Pattern Matching Questions
Advanced string algorithms for coding interviews: substring search (naive baseline, KMP including streaming use, Rabin-Karp with collision-resistant hashing, Z-algorithm, Boyer-Moore), multiple-pattern matching (Aho-Corasick, including large automata and updates under memory limits), suffix arrays (doubling construction, binary-search queries, Kasai LCP), suffix trees (Ukkonen) and suffix automata, repeated, common and distinct-substring problems (suffix array plus LCP, binary search on length with a rolling hash), the Burrows-Wheeler transform and FM-index, palindromic structures (Manacher), minimal string rotation (Booth), approximate matching beyond the textbook recurrence (banded and bit-parallel edit distance, matching with k mismatches), wildcard and regular-expression matching including backtracking engines, catastrophic backtracking and its mitigations, and string applications built on a trie (multi-pattern dictionaries, autocomplete and prefix search at scale). Also covers Unicode-aware matching and normalization, and adversarial inputs such as hash collisions and the cost of each defence. Boundary: introductory string manipulation, the trie as a data structure, edit-distance and subsequence recurrences, hash-map counting problems, generic data cleaning, NLP pipelines and test-plan design are covered elsewhere.
Rabin-Karp can return false positives when two different windows share a hash. Implement a version in C++ that stays correct and makes a collision unlikely even on adversarially chosen input, and explain how you chose the hashing parameters and what the expected cost is.
Sample Answer
The idea in plain words
Rabin-Karp slides a window of the pattern's length over the text and compares a number (a hash, a short fingerprint of the window) instead of comparing characters. The hash can be updated in constant time when the window moves one step (a rolling hash). Different windows can share a hash (a collision), so a fingerprint match is only a suspect. Two things make the program both correct and hard to attack:
- Verify every hit. When the fingerprints match, compare the actual characters. A false positive then costs time but can never produce a wrong answer. This is what makes the result always correct.
- Make the hash unpredictable. If the base and modulus are fixed in the source, anyone who has read the code can craft strings that collide. Pick the base at random on every run, and use two independent (modulus, base) pairs so a collision has to happen in both at once.
Why the textbook version is not enough
The common version uses one fixed base and lets the 64-bit unsigned integer overflow, which silently means arithmetic modulo 2^64. That hash has a known break: the Thue-Morse string (a two-letter sequence whose i-th letter is a or b according to whether the number of 1 bits in i is even or odd, starting abbabaab...) of length 2^11 and its letter-swapped complement have the same hash modulo 2^64 for every odd base, so changing the base constant does not help. The section "Why a power-of-two modulus fails" below shows the mechanism with a printed table. The program below shows it: the fixed-base version reports a match at position 0 that is not a match. It also skips verification, which is why it is wrong rather than merely slow.
Choosing the parameters
The hash of a window is the polynomial c_0 * B^(m-1) + c_1 * B^(m-2) + ... + c_(m-1) taken modulo a prime p, where m is the pattern length and B is the base.
- Modulus: a prime near 10^9. Two windows with different characters give two different polynomials. Their difference, seen as a function of the base B, is a polynomial that is not identically zero and has degree at most m-1. Modulo a prime p, such a polynomial has at most m-1 roots (values of B that make it zero), the same way a quadratic has at most 2 roots; this holds because arithmetic mod a prime lets you divide by any nonzero value, which a power-of-two modulus does not. The two windows collide only if B happens to be one of those roots. With B drawn uniformly at random (every value in range equally likely), the chance of that is at most (m-1)/(p-256), because the code draws the base from the p-256 values 256 to p-1. That is within one part in a million of (m-1)/p, so the figures below use (m-1)/p. Both values stay below 2^30, so a product of two of them stays below 2^60 and never overflows
uint64_t. - Base: random, fresh per call, not a constant. The adversary may know the moduli but not B, so no input can be built against it. Bases start at 256 so every byte value is a distinct digit.
- Two independent pairs. With p1 = 1,000,000,007 and p2 = 998,244,353 and independent random bases, the false-positive chance for one pair of windows is at most (m-1)^2 / (p1 * p2): the two bases are drawn independently, so the probability that both fall on a root is the product of the two single chances, (m-1)/p1 times (m-1)/p2. For m = 2048 that is (2047/1,000,000,007) * (2047/998,244,353) = 2.05e-6 * 2.05e-6 = 4.2e-12. The union bound says the chance that at least one of several bad events happens is at most the sum of their separate chances, so over n = 1,000,000 windows the chance that any window is a false positive is at most 1,000,000 * 4.2e-12 = 4.2e-6. All three figures are printed by the second program below.
- A single modulus 2^61 - 1 (a Mersenne prime, a prime of the form 2^k - 1) with a 128-bit multiply gives (m-1)/(2^61-1) = 8.9e-16 for m = 2048 with one pair, and is a good alternative where
unsigned __int128is available. The product of two 61-bit values needs up to 122 bits, so it is computed inunsigned __int128and reduced with%:(u64)((u128)a * b % M61), shown in the second program.unsigned __int128is a GCC and Clang extension, not standard C++.
Because every hit is verified, these probabilities affect speed only, never correctness.
The code
#include <cstdint>
#include <iostream>
#include <random>
#include <string>
#include <vector>
using namespace std;
using u64 = uint64_t;
using u128 = unsigned __int128;
constexpr u64 MOD1 = 1'000'000'007ULL;
constexpr u64 MOD2 = 998'244'353ULL;
struct Result {
vector<size_t> positions;
size_t fingerprint_hits = 0; // windows whose double hash matched
size_t false_positives = 0; // hits rejected by the character check
};
Result rabin_karp(const string& text, const string& pat) {
Result r;
size_t n = text.size(), m = pat.size();
if (m == 0 || m > n) return r;
// Fresh random bases on every call: the input cannot be tuned to them.
random_device rd;
mt19937_64 gen(((u64)rd() << 32) ^ rd());
u64 b1 = 256 + gen() % (MOD1 - 256);
u64 b2 = 256 + gen() % (MOD2 - 256);
u64 h1 = 0, h2 = 0, w1 = 1, w2 = 1; // w = base^(m-1)
for (size_t i = 0; i < m; i++) {
h1 = (h1 * b1 + (unsigned char)pat[i]) % MOD1;
h2 = (h2 * b2 + (unsigned char)pat[i]) % MOD2;
if (i + 1 < m) { w1 = w1 * b1 % MOD1; w2 = w2 * b2 % MOD2; }
}
u64 t1 = 0, t2 = 0;
for (size_t i = 0; i < m; i++) {
t1 = (t1 * b1 + (unsigned char)text[i]) % MOD1;
t2 = (t2 * b2 + (unsigned char)text[i]) % MOD2;
}
for (size_t i = 0;; i++) {
if (t1 == h1 && t2 == h2) {
r.fingerprint_hits++;
if (text.compare(i, m, pat) == 0) r.positions.push_back(i);
else r.false_positives++;
}
if (i + m >= n) break;
u64 out = (unsigned char)text[i], in = (unsigned char)text[i + m];
t1 = ((t1 + MOD1 - out * w1 % MOD1) % MOD1 * b1 + in) % MOD1;
t2 = ((t2 + MOD2 - out * w2 % MOD2) % MOD2 * b2 + in) % MOD2;
}
return r;
}
// Textbook version: fixed base, arithmetic mod 2^64 (unsigned overflow), no verification.
vector<size_t> naive_fixed_hash(const string& text, const string& pat) {
vector<size_t> out;
size_t n = text.size(), m = pat.size();
const u64 B = 131;
u64 w = 1, h = 0, t = 0;
for (size_t i = 0; i < m; i++) { h = h * B + (unsigned char)pat[i]; t = t * B + (unsigned char)text[i]; if (i + 1 < m) w *= B; }
for (size_t i = 0;; i++) {
if (t == h) out.push_back(i);
if (i + m >= n) break;
t = (t - (unsigned char)text[i] * w) * B + (unsigned char)text[i + m];
}
return out;
}
string thue_morse(int k, bool complement) {
string s;
for (size_t i = 0; i < (1u << k); i++) s += ((__builtin_popcountll(i) & 1) ^ complement) ? 'b' : 'a';
return s;
}
int main() {
string pat = thue_morse(11, false);
string text = thue_morse(11, true) + "xyz" + pat; // one real match, at index 2051
auto naive = naive_fixed_hash(text, pat);
cout << "fixed base, mod 2^64: reported";
for (size_t p : naive) cout << ' ' << p;
cout << '\n';
Result r = rabin_karp(text, pat);
cout << "random double hash: reported";
for (size_t p : r.positions) cout << ' ' << p;
cout << ", fingerprint hits " << r.fingerprint_hits << ", false positives " << r.false_positives << '\n';
string t2 = "abracadabra abracadabra", p2 = "abra";
Result q = rabin_karp(t2, p2);
cout << "abra in text:";
for (size_t p : q.positions) cout << ' ' << p;
cout << '\n';
Result e = rabin_karp("aaaa", "aaa");
cout << "overlap aaa in aaaa:";
for (size_t p : e.positions) cout << ' ' << p;
cout << '\n';
Result z = rabin_karp("abc", ""), y = rabin_karp("ab", "abc"), w = rabin_karp("abc", "abc");
cout << "empty pattern: " << z.positions.size() << " positions, pattern longer than text: "
<< y.positions.size() << " positions, pattern equal to text:";
for (size_t p : w.positions) cout << ' ' << p;
cout << '\n';
}
Output
Run in a python:3.12 container (g++ 14.2.0), compiled with g++ -std=c++17 -O2, it prints:
fixed base, mod 2^64: reported 0 2051
random double hash: reported 2051, fingerprint hits 1, false positives 0
abra in text: 0 7 12 19
overlap aaa in aaaa: 0 1
empty pattern: 0 positions, pattern longer than text: 0 positions, pattern equal to text: 0
The first line is the break of the textbook hash: the pattern is the Thue-Morse string of length 2048, the text starts with its complement, then "xyz", then the pattern, so the only real match is at 2051. The fixed-base hash also reports 0, a false positive. The randomized double hash reports 2051 only, and its single fingerprint hit was the real match.
Why a power-of-two modulus fails
Letting uint64_t overflow means every result is reduced modulo 2^64, and 2^64 is not a prime: it has no division by even numbers. Write a for 0 and b for 1 (the real letters differ by exactly 1 as well, which only scales the difference). The hash of the Thue-Morse string of length 2^k minus the hash of its complement is, up to sign, the product (B - 1)(B^2 - 1)(B^4 - 1)...(B^(2^(k-1)) - 1). For k = 2 the strings are abba and baab, and the product is (B - 1)(B^2 - 1). For any odd B every factor is even, and each squaring adds another power of 2 to the factor: B^2 - 1 is divisible by 8, B^4 - 1 by 16, B^8 - 1 by 32, and so on. Multiplying k such factors piles up more and more factors of 2, and once the product has at least 64 factors of 2 it is 0 modulo 2^64. For k = 10 the guaranteed count is 1 + 3 + 4 + ... + 11 = 64, so every odd base fails from length 1024 up, and the base is irrelevant. The second program prints, for several bases, how many trailing zero bits (factors of 2) the hash difference has; "64 (equal)" means the two hashes are identical.
A prime modulus has no such trap: a product of nonzero values mod a prime is never zero, so only the at most m-1 roots from the bound above can cause a collision.
Small numbers you can follow by hand
The first part of the next program uses digits as characters, base B = 10 and the tiny prime modulus 13, so the whole rolling hash fits on paper. Pattern 23 hashes to 23 mod 13 = 10. The first window 62 is 62 mod 13 = 10: a collision, so the character check rejects it. Sliding to the next window removes the outgoing digit 6 (its weight is 10, so subtract 6 * 10), shifts, and adds the incoming 3: (62 - 60) * 10 + 3 = 23, hash 10, a true match. Sliding again: (23 - 20) * 10 + 5 = 35, hash 9, no match. The real code does this with two large primes instead of 13, so collisions become astronomically rare. The remaining parts print the Thue-Morse table and the probability figures quoted above.
#include <cstdint>
#include <cstdio>
#include <string>
using namespace std;
using u64 = uint64_t;
using u128 = unsigned __int128;
// Part 1: a hash you can follow with a pencil. Digits are the characters, base 10, modulus 13.
void toy() {
const int B = 10, P = 13;
string text = "6235", pat = "23";
int m = pat.size(), w = B; // w = B^(m-1) = 10
int hp = 0, t = 0;
for (char c : pat) hp = (hp * B + (c - '0')) % P;
for (int i = 0; i < m; i++) t = (t * B + (text[i] - '0')) % P;
printf("pattern %s hashes to %d\n", pat.c_str(), hp);
for (int i = 0;; i++) {
bool same = text.compare(i, m, pat) == 0;
printf("window %s at %d: hash %d%s\n", text.substr(i, m).c_str(), i, t,
t == hp ? (same ? " hash match, characters match" : " hash match, characters differ (false positive)") : "");
if (i + m >= (int)text.size()) break;
int out = text[i] - '0', in = text[i + m] - '0';
t = ((t + P - out * w % P) % P * B + in) % P;
}
}
// Part 2: why mod 2^64 breaks. Hash of the Thue-Morse string (a = 0, b = 1 digits) and of its complement.
string tm(int k, bool comp) {
string s;
for (size_t i = 0; i < (1u << k); i++) s += ((__builtin_popcountll(i) & 1) ^ comp) ? 'b' : 'a';
return s;
}
u64 poly(const string& s, u64 B) { u64 h = 0; for (char c : s) h = h * B + (unsigned char)c; return h; }
void thue() {
printf("k=2 strings: %s and %s\n", tm(2, false).c_str(), tm(2, true).c_str());
const u64 bases[] = {3, 131, 65537};
for (int k = 1; k <= 11; k++) {
string x = tm(k, false), y = tm(k, true);
printf("k=%2d length %4d:", k, 1 << k);
for (u64 B : bases) {
u64 d = poly(x, B) - poly(y, B); // difference modulo 2^64
printf(" base %5llu: %2d trailing zero bits%s", (unsigned long long)B,
d == 0 ? 64 : __builtin_ctzll(d), d == 0 ? " (equal)" : "");
}
printf("\n");
}
}
// Part 3: modulus 2^61 - 1 with a 128-bit product.
const u64 M61 = (1ULL << 61) - 1;
u64 mulmod61(u64 a, u64 b) { return (u64)((u128)a * b % M61); }
int main() {
toy();
thue();
printf("mulmod61(2^60, 2^60) = %llu\n", (unsigned long long)mulmod61(1ULL << 60, 1ULL << 60));
double q = 2047.0;
printf("per pair, one prime: %.2e and %.2e; both: %.2e; over 1e6 windows: %.2e; mod 2^61-1: %.2e\n",
q / 1000000007.0, q / 998244353.0, q / 1000000007.0 * q / 998244353.0,
1e6 * (q / 1000000007.0) * (q / 998244353.0), q / (double)M61);
}
Output (same g++ 14.2.0 and flags as above):
pattern 23 hashes to 10
window 62 at 0: hash 10 hash match, characters differ (false positive)
window 23 at 1: hash 10 hash match, characters match
window 35 at 2: hash 9
k=2 strings: abba and baab
k= 1 length 2: base 3: 1 trailing zero bits base 131: 1 trailing zero bits base 65537: 16 trailing zero bits
k= 2 length 4: base 3: 4 trailing zero bits base 131: 4 trailing zero bits base 65537: 33 trailing zero bits
k= 3 length 8: base 3: 8 trailing zero bits base 131: 8 trailing zero bits base 65537: 51 trailing zero bits
k= 4 length 16: base 3: 13 trailing zero bits base 131: 13 trailing zero bits base 65537: 64 trailing zero bits (equal)
k= 5 length 32: base 3: 19 trailing zero bits base 131: 19 trailing zero bits base 65537: 64 trailing zero bits (equal)
k= 6 length 64: base 3: 26 trailing zero bits base 131: 26 trailing zero bits base 65537: 64 trailing zero bits (equal)
k= 7 length 128: base 3: 34 trailing zero bits base 131: 34 trailing zero bits base 65537: 64 trailing zero bits (equal)
k= 8 length 256: base 3: 43 trailing zero bits base 131: 43 trailing zero bits base 65537: 64 trailing zero bits (equal)
k= 9 length 512: base 3: 53 trailing zero bits base 131: 53 trailing zero bits base 65537: 64 trailing zero bits (equal)
k=10 length 1024: base 3: 64 trailing zero bits (equal) base 131: 64 trailing zero bits (equal) base 65537: 64 trailing zero bits (equal)
k=11 length 2048: base 3: 64 trailing zero bits (equal) base 131: 64 trailing zero bits (equal) base 65537: 64 trailing zero bits (equal)
mulmod61(2^60, 2^60) = 576460752303423488
per pair, one prime: 2.05e-06 and 2.05e-06; both: 4.20e-12; over 1e6 windows: 4.20e-06; mod 2^61-1: 8.88e-16
Read-out: the toy section shows one false positive (window 62) and one true match. In the table, bases 3 and 131 need k = 10 to reach 64 zero bits (their counts rise 13, 19, 26, 34, 43, 53 and then reach 64), matching the factor-of-2 count above, while base 65537 = 2^16 + 1 hits 64 already at k = 4 because B - 1 itself is divisible by 2^16. The last line gives the quoted probabilities: 2.05e-6 per prime, 4.2e-12 for both, 4.2e-6 over a million windows, 8.88e-16 for the 2^61 - 1 alternative. A coding round usually needs only the verified rolling hash with a random base modulo a prime; the factor-of-2 argument and the 128-bit modulus are deeper material that interviewers rarely ask for.
Trace on a small input
For text "aaaa" and pattern "aaa" the windows are at 0 and 1. Both have the same characters, so both fingerprints equal the pattern's, both are verified by text.compare, and both are reported: 0 1. Overlapping matches are found because the window advances one character at a time.
Expected cost
- Hashing: building the pattern hash and first window hash is O(m); each slide is O(1) with two modular steps, so O(n) for the slides. Total O(n + m).
- Verification: each hit costs O(m). A true match is always verified, so the cost is O(occurrences * m). A false hit happens with probability at most about 4.2e-12 per window for m = 2048, so the expected extra work from false hits is n * 4.2e-12 * m, which is negligible.
- Expected total when matches are rare: O(n + m). Worst case: O(n * m), reached when matches are plentiful, such as text of n copies of 'a' with a pattern of m copies of 'a', because every window really matches and is verified. If the question only needs "does a match exist", stop at the first verified hit.
- Space: O(1) beyond the output list.
Edge cases
- Empty pattern or pattern longer than the text returns no positions (the code returns early, and the program prints both cases, along with a pattern equal to the whole text).
- Overlapping matches ("aaa" in "aaaa") are reported.
- Subtracting the outgoing character adds the modulus first (
t + MOD - out * w % MOD) so the value never goes negative on unsigned types. (unsigned char)casts keep bytes above 127 from becoming negative numbers.
Common mistakes
- Relying on
uint64_toverflow as the modulus (breakable as shown) and a hard-coded base. - Seeding the random generator with a constant or the clock second: the adversary only needs to guess it.
- Skipping verification and accepting a hash match as a match.
- Multiplying two 62-bit values in
uint64_tfor a large modulus, which overflows.
Running the code
g++ -std=c++17 -O2 -Wall -o rabin_karp rabin_karp.cpp && ./rabin_karp
Save the listing as rabin_karp.cpp. No other files or libraries are needed.
You need to count occurrences of thousands of short patterns across a very long text. Compare running a separate search per pattern against building a single automaton for all patterns. When does each win, and when is it not worth hand-writing the automaton and better to use an optimised library?
Sample Answer
Recommendation
For thousands of short patterns over a very long text, build one Aho-Corasick automaton and read the text once; in production code, use a maintained library for it rather than writing your own. Hand-write it only when you need behaviour a library does not give you or cannot install one. A separate search per pattern wins only when there are very few patterns, or when the text can be indexed once and searched many times.
An Aho-Corasick automaton is a trie (a tree whose paths spell the patterns) with failure links that tell the scan where to continue after a mismatch, so the text is never re-read.
Cost model
Let N be the text length, k the number of patterns, P the total length of all patterns, and z the number of matches you must list.
| Approach | Preprocessing | Search | Memory |
|---|---|---|---|
| One search per pattern (KMP or Z, linear per pattern) | O(P) | O(k * N) character reads | O(longest pattern) |
| One search per pattern (Boyer-Moore style, skipping) | O(P + alphabet) | about O(k * N / m) on typical text for pattern length m, O(k * N * m) worst | small |
| One automaton | O(P) | O(N + z) | O(P) nodes |
KMP (Knuth-Morris-Pratt) and Z are linear-time single-pattern searches, and Boyer-Moore skips ahead using the text character where a comparison failed; for this decision only their cost shape matters: each reads about the whole text once, and you pay that once per pattern. The reason the automaton wins at scale is that k leaves the text term: the work per text character is constant on average over the whole run (this is what amortized means: occasional expensive steps are paid for by the cheap ones around them), not proportional to the number of patterns. z is the matches you list. If you only need counts per pattern, you can drop z too: add one to a counter for the node reached after each character, then push counts up the failure links from the deepest nodes to the shallowest. That is the count path, worked on a tiny input after the measured example.
Measured on a pinned example
The program below counts overlapping occurrences of k = 300 random 4-letter patterns over a random 50,000-character text on an 8-letter alphabet, with seeded random numbers. It also asserts that the counts equal those from a separate regular-expression scan per pattern.
import random
import re
from collections import deque
def count_all(patterns, text):
"""Occurrences (overlaps included) of every pattern, in one pass over the text."""
nxt, fail, end = [{}], [0], {}
for pid, p in enumerate(patterns):
node = 0
for ch in p:
if ch not in nxt[node]:
nxt.append({})
fail.append(0)
nxt[node][ch] = len(nxt) - 1
node = nxt[node][ch]
end.setdefault(node, []).append(pid)
order, queue = [], deque(nxt[0].values())
while queue:
u = queue.popleft()
order.append(u)
for ch, v in nxt[u].items():
f = fail[u]
while f and ch not in nxt[f]:
f = fail[f]
fail[v] = nxt[f].get(ch, 0)
queue.append(v)
visits, node, hops = [0] * len(nxt), 0, 0
for ch in text:
while node and ch not in nxt[node]:
node = fail[node]
hops += 1
node = nxt[node].get(ch, 0)
visits[node] += 1 # only count the visit now
for u in reversed(order): # deepest first: a visit to u is also a visit to its suffix nodes
visits[fail[u]] += visits[u]
counts = [0] * len(patterns)
for node, pids in end.items():
for pid in pids:
counts[pid] = visits[node]
return counts, len(nxt) - 1, hops
def per_pattern(patterns, text):
return [len(re.findall("(?=" + re.escape(p) + ")", text)) for p in patterns]
if __name__ == "__main__":
rng = random.Random(11)
n, k, m = 50_000, 300, 4
text = "".join(rng.choice("abcdefgh") for _ in range(n))
patterns = ["".join(rng.choice("abcdefgh") for _ in range(m)) for _ in range(k)]
counts, nodes, hops = count_all(patterns, text)
assert counts == per_pattern(patterns, text)
print(f"text length N={n}, patterns k={k}, total pattern length P={k * m}")
print(f"automaton: {nodes} trie nodes, {n} transitions + {hops} failure hops = {n + hops} steps")
print(f"separate scans: {k} x {n} = {k * n} character positions visited")
print(f"total occurrences counted: {sum(counts)}")
Run in a python:3.12 container (Python 3.12.15), it prints:
text length N=50000, patterns k=300, total pattern length P=1200
automaton: 598 trie nodes, 50000 transitions + 47962 failure hops = 97962 steps
separate scans: 300 x 50000 = 15000000 character positions visited
total occurrences counted: 3564
The automaton does 97,962 steps (50,000 transitions, one trie edge followed per text character, plus 47,962 failure hops, each a fallback along a failure link after a mismatch) for all 300 patterns, versus 300 x 50,000 = 15,000,000 character positions for one full pass per pattern, about 153 times fewer. A skipping algorithm like Boyer-Moore reads fewer than all positions per pattern, so the gap against that baseline is smaller, but with 4-letter patterns the skips are short.
The count path on a tiny input
Patterns he, she, hers against the text ushers. The scan only adds 1 to the node it lands on after each character: s, sh, she, her, hers are each visited once (the first character u leaves it at the root). That alone would count she and hers correctly but miss he, which ended inside she. A visit to a node is also a visit to every node on its failure chain, because those are suffixes of the text just read; she fails to he, so pushing the count from she to he credits he with the occurrence. Processing the nodes deepest first guarantees a node's count is complete before it is pushed further up. Here is that walk-through as code, with every step printed:
from collections import deque
def count_walkthrough(patterns, text):
nxt, fail, name = [{}], [0], [""]
for p in patterns:
node = 0
for ch in p:
if ch not in nxt[node]:
nxt.append({})
fail.append(0)
name.append(name[node] + ch)
nxt[node][ch] = len(nxt) - 1
node = nxt[node][ch]
order, queue = [], deque(nxt[0].values())
while queue:
u = queue.popleft()
order.append(u)
for ch, v in nxt[u].items():
f = fail[u]
while f and ch not in nxt[f]:
f = fail[f]
fail[v] = nxt[f].get(ch, 0)
queue.append(v)
visits, node = [0] * len(nxt), 0
for ch in text:
while node and ch not in nxt[node]:
node = fail[node]
node = nxt[node].get(ch, 0)
visits[node] += 1
print("visits after the scan :", {name[u]: visits[u] for u in order if visits[u]})
for u in reversed(order): # deepest nodes first
if visits[u]:
print(f" push {visits[u]} from {name[u]!r} to its failure target {name[fail[u]]!r}")
visits[fail[u]] += visits[u]
print("visits after the push :", {name[u]: visits[u] for u in order if visits[u]})
return {p: visits[next(u for u in order if name[u] == p)] for p in patterns}
print(count_walkthrough(["he", "she", "hers"], "ushers"))
Output (Python 3.12, python:3.12 container):
visits after the scan : {'s': 1, 'sh': 1, 'her': 1, 'she': 1, 'hers': 1}
push 1 from 'hers' to its failure target 's'
push 1 from 'she' to its failure target 'he'
push 1 from 'her' to its failure target ''
push 1 from 'sh' to its failure target 'h'
push 1 from 'he' to its failure target ''
push 2 from 's' to its failure target ''
push 1 from 'h' to its failure target ''
visits after the push : {'h': 1, 's': 2, 'he': 1, 'sh': 1, 'her': 1, 'she': 1, 'hers': 1}
{'he': 1, 'she': 1, 'hers': 1}
The last line is the per-pattern count: he once (inside she, at index 2), she once, hers once.
When each wins
- Per-pattern search wins when k is small (a handful of patterns), when the platform's built-in substring search is vectorised native code (compiled code that processes many characters per CPU instruction) and your automaton would be interpreted code, when patterns change constantly and building the trie each time is not amortised, or when the text is static and queried with many different patterns: build a suffix array (a sorted list of all suffix start positions of the text) once, and each pattern then costs about O(m log N): a binary search makes about log N probes and each probe compares up to m characters of the pattern with a suffix. The suffix array route is the heavier tool: it pays off only when the same text is searched many times.
- The automaton wins when the pattern set is large and fixed, the text is long or arrives as a stream (it keeps one state and O(P) memory, and can carry the state across chunks), and you need every pattern in one pass.
When not to hand-write it
Use an optimised library when:
- the pattern set is large or changes often and you want a tested implementation: the
aho-corasickcrate in Rust,pyahocorasickin Python, and fixed-string multi-pattern modes of command-line tools (grep -F -f patterns.txt) exist for exactly this; - you need case folding, Unicode handling, word boundaries or regular-expression features, which libraries and engines such as RE2 (Google's regular-expression engine, built to avoid backtracking) handle and a naive automaton does not;
- memory matters: libraries pack the automaton into arrays, where a dict-per-node version in Python spends at least 64 bytes on every node (the size of an empty dict in CPython 3.12, 184 bytes with one entry);
- speed matters: a compiled implementation is much faster than interpreted Python, and the matching loop is the hot loop.
Hand-write it when an interview asks for it, when no suitable library exists for the platform (embedded, restricted runtime), or when you need custom semantics: the leftmost-longest rule, per-pattern weights, or state stored between calls. The leftmost-longest rule means that when several patterns match starting at the same text position, the longest one is the one reported.
A regular-expression alternation p1|p2|...|pk is not a substitute on a backtracking engine such as Python's re: it tries alternatives one after another at each text position (a backtracking engine tries one choice and, if the rest fails, goes back and tries the next), so the cost grows with k. Engines with linear-time guarantees (RE2) compile alternations into an automaton.
Pitfalls
- Counting overlapping occurrences: the count path above includes overlaps and shorter patterns nested inside longer ones, because a visit to a node also counts for its suffix nodes.
- Building the trie from patterns that share long prefixes: fine, nodes are shared.
- Reporting z matches when only counts are needed.
Running the code
python cnt.py
python tiny.py
Save the listings as cnt.py and tiny.py. It uses only the standard library (random, re, collections).
Implement the Aho-Corasick automaton for multiple-pattern matching. Provide an API with build(patterns: List[str]) and search(text: str) -> List[(pattern_id, index)]. Explain how failure links and output links work, and give complexity in terms of total pattern length P and text length N.
Sample Answer
The idea in plain words
To look for many patterns at once, put all of them into one trie (a tree where each edge is a character and each path from the root spells a prefix of some pattern). Walking the text through the trie follows one pattern at a time, but on a mismatch we do not want to restart: if we have just read "she" and the next character does not continue "she", the useful part of what we read is its longest suffix that is still a prefix of some pattern (here "he"). A failure link points from each trie node to exactly that node. With failure links the walk never moves backwards in the text, which is the same trick KMP (Knuth-Morris-Pratt, the classic single-pattern matcher that keeps a fallback table for its one pattern) uses. An output link handles patterns nested inside others: from a node it jumps to the nearest node on the failure chain that ends some pattern, so every match ending at the current character is reported without scanning the whole chain.
Brute force
Run a single-pattern search for each of k patterns: O(k * N) at best for a text of length N, even with KMP, and the text is read k times. The automaton reads the text once.
Approach, step by step
- Build the trie. Insert every pattern; the node where a pattern ends stores that pattern's id (duplicate patterns share a node and keep both ids).
- Failure links by breadth-first search (visit every node of depth 1, then every node of depth 2, and so on, using a queue). Depth-1 nodes fail to the root. For a child reached from node u by character ch: start at fail[u] and follow failure links until a node has an edge on ch; the child's failure link is that edge's target (or the root if none). Processing by depth guarantees fail[u] is ready before its children need it.
By hand, for the node she: its parent is sh, and the failure link of sh is h (the longest proper suffix of "sh", meaning a suffix that is not the whole string, that is also a trie node). The loop asks whether h has an edge on e. It does (h -> he), so the failure link of she is he, and the printed line is fail of 'she': try ['h'] for an edge 'e' -> 'he'. The same read-out for sh is try [''] for an edge 'h' -> 'h': the parent s fails to the root, the root has an edge on h, and that edge leads to h. When the first candidate has no edge, the loop hops again. The second example in the output, patterns aaab and ab, shows it: for aaab the candidates tried are aa (no edge on b), then a (has edge b), giving the failure link ab, printed as fail of 'aaab': try ['aa', 'a'] for an edge 'b' -> 'ab'.
3. Output links. out_link[child] is fail[child] if that node ends a pattern, else out_link[fail[child]]. Following out_links only visits nodes that really end a pattern.
4. Search. For each text character, follow failure links until some edge accepts it (or you are at the root), move along that edge, then report every pattern ending at this node and along its out_link chain. A pattern of length L matched at text index i started at i - L + 1.
The code
import random
from collections import deque
from typing import List, Tuple
class AhoCorasick:
def __init__(self):
self.next = [{}] # next[node][char] -> child node (the trie)
self.fail = [0] # failure link: longest proper suffix of this node's string that is also a trie node
self.out = [[]] # ids of patterns that end exactly at this node
self.out_link = [-1] # nearest node on the failure chain that has a non-empty out (output link)
self.lengths = [] # lengths[pattern_id]
self.word = [""] # word[node] = the string spelled from the root to this node (for display)
def build(self, patterns: List[str], trace: bool = False) -> None:
for pid, pat in enumerate(patterns):
if not pat:
raise ValueError("empty patterns are not supported")
node = 0
for ch in pat:
if ch not in self.next[node]:
self.next.append({})
self.fail.append(0)
self.out.append([])
self.out_link.append(-1)
self.word.append(self.word[node] + ch)
self.next[node][ch] = len(self.next) - 1
node = self.next[node][ch]
self.out[node].append(pid) # duplicates share a node and both ids are kept
self.lengths.append(len(pat))
queue = deque(self.next[0].values()) # depth-1 nodes fail to the root
while queue: # breadth first: shallower nodes are finished first
node = queue.popleft()
for ch, child in self.next[node].items():
f = self.fail[node]
tried = [f]
while f and ch not in self.next[f]:
f = self.fail[f]
tried.append(f)
self.fail[child] = self.next[f].get(ch, 0)
if trace:
print(f"fail of {self.word[child]!r}: try {[self.word[x] for x in tried]} for an edge {ch!r}"
f" -> {self.word[self.fail[child]]!r}")
fl = self.fail[child]
self.out_link[child] = fl if self.out[fl] else self.out_link[fl]
queue.append(child)
def search(self, text: str, visited: list = None) -> List[Tuple[int, int]]:
"""Return (pattern_id, start_index) for every occurrence, overlaps included."""
found, node = [], 0
for i, ch in enumerate(text):
while node and ch not in self.next[node]:
node = self.fail[node] # fall back until some suffix can take ch
node = self.next[node].get(ch, 0)
if visited is not None:
visited.append(node) # record the state after each character
hit = node if self.out[node] else self.out_link[node]
while hit != -1: # walk only nodes that really end a pattern
for pid in self.out[hit]:
found.append((pid, i - self.lengths[pid] + 1))
hit = self.out_link[hit]
return found
def brute(patterns, text):
return sorted((pid, i) for pid, p in enumerate(patterns)
for i in range(len(text) - len(p) + 1) if text.startswith(p, i))
if __name__ == "__main__":
demo = AhoCorasick()
demo.build(["aaab", "ab"], trace=True) # a failure link that needs two hops
patterns = ["he", "she", "his", "hers"]
ac = AhoCorasick()
ac.build(patterns, trace=True)
# label each node with its string, for display
label = {0: ""}
stack = [0]
while stack:
u = stack.pop()
for ch, v in ac.next[u].items():
label[v] = label[u] + ch
stack.append(v)
for v in sorted(label, key=lambda v: (len(label[v]), label[v])):
if v:
ol = ac.out_link[v]
print(f"node {label[v]!r:7} fail -> {label[ac.fail[v]]!r:5} ends {[patterns[p] for p in ac.out[v]]} out_link -> {label[ol] if ol != -1 else None!r}")
text = "ushers"
visited = []
result = ac.search(text, visited)
for i, (ch, node) in enumerate(zip(text, visited)):
print(f"after {text[:i + 1]!r}: state {label[node]!r}")
print("matches (pattern_id, start):", result)
print("as words:", [(patterns[p], s) for p, s in result])
try:
AhoCorasick().build(["he", ""])
except ValueError as err:
print("empty pattern:", err)
rng = random.Random(5)
for _ in range(1000):
pats = ["".join(rng.choice("ab") for _ in range(rng.randint(1, 4))) for _ in range(rng.randint(1, 5))]
txt = "".join(rng.choice("ab") for _ in range(rng.randint(0, 15)))
a = AhoCorasick()
a.build(pats)
assert sorted(a.search(txt)) == brute(pats, txt), (pats, txt)
print("1000 random cases (with duplicate and nested patterns) agree with brute force")
Output
Run in a python:3.12 container (Python 3.12.15), it prints:
fail of 'aa': try [''] for an edge 'a' -> 'a'
fail of 'ab': try [''] for an edge 'b' -> ''
fail of 'aaa': try ['a'] for an edge 'a' -> 'aa'
fail of 'aaab': try ['aa', 'a'] for an edge 'b' -> 'ab'
fail of 'he': try [''] for an edge 'e' -> ''
fail of 'hi': try [''] for an edge 'i' -> ''
fail of 'sh': try [''] for an edge 'h' -> 'h'
fail of 'her': try [''] for an edge 'r' -> ''
fail of 'his': try [''] for an edge 's' -> 's'
fail of 'she': try ['h'] for an edge 'e' -> 'he'
fail of 'hers': try [''] for an edge 's' -> 's'
node 'h' fail -> '' ends [] out_link -> None
node 's' fail -> '' ends [] out_link -> None
node 'he' fail -> '' ends ['he'] out_link -> None
node 'hi' fail -> '' ends [] out_link -> None
node 'sh' fail -> 'h' ends [] out_link -> None
node 'her' fail -> '' ends [] out_link -> None
node 'his' fail -> 's' ends ['his'] out_link -> None
node 'she' fail -> 'he' ends ['she'] out_link -> 'he'
node 'hers' fail -> 's' ends ['hers'] out_link -> None
after 'u': state ''
after 'us': state 's'
after 'ush': state 'sh'
after 'ushe': state 'she'
after 'usher': state 'her'
after 'ushers': state 'hers'
matches (pattern_id, start): [(1, 1), (0, 2), (3, 2)]
as words: [('she', 1), ('he', 2), ('hers', 2)]
empty pattern: empty patterns are not supported
1000 random cases (with duplicate and nested patterns) agree with brute force
Worked trace: patterns he, she, his, hers on "ushers"
The pattern ids are 0 to 3 in that order. The automaton has 9 nodes below the root. The printed state after each character shows how the walk goes:
- After "us" the state is
sand after "ush" it issh. - After "ushe" the state is
she. That node ends pattern 1 (she); the current index is 3, so the start is 3 - 3 + 1 = 1. Its out_link points tohe, so pattern 0 (he) is also reported, at start 3 - 2 + 1 = 2. - Next character
r:shehas no edge on r. The failure link ofsheishe, andhehas an edge on r, so the state becomesher. No text character was re-read. - After "ushers" the state is
hers, which ends pattern 3 (hers) at index 5, so the start is 5 - 4 + 1 = 2.
The result is [(1, 1), (0, 2), (3, 2)], that is she at 1, he at 2, hers at 2. Overlapping matches (he inside she, he as the start of hers) are all reported, which is what the output links are for.
Complexity
Let P be the total length of all patterns, N the text length and z the number of matches reported.
- Build: O(P) trie nodes and edges. The failure-link computation is also O(P) overall by amortized analysis (counting the cost over the whole run instead of per step), the same argument KMP uses: walking down one pattern's path, the depth of the failure target (how many characters long the string it names is) rises by at most one per step, and each extra hop in the while loop strictly lowers it, so the hops cannot outnumber the rises. For
hersthe target depths are 0 (h), 0 (he), 0 (her), 1 (hers->s): a total rise of 1, so at most 1 hop was ever available to spend. The time assumes a hash map per node (a dictionary from character to child node, as the code uses; a full table of one slot per alphabet symbol per node would cost O(P * alphabet size)). - Search: O(N + z); the bound depends on z, the number of matches reported, which is why it is called output-sensitive. The depth of the current state (the length of the string it names) rises by at most one per text character and every failure hop lowers it, so the failure hops across the whole text number at most N. On "ushers" the depths after each character are 0, 1, 2, 3, 3, 4 (from the printed states
'',s,sh,she,her,hers): atrthe state falls from depth 3 (she) to 2 (he) with one hop and then rises to 3 (her). Depth was gained on 5 of the 6 characters (uhas no edge from the root and gains nothing) and the single hop spent 1 of that gain, so the number of hops can never exceed the total gain, which can never exceed N. The output-link walk does constant work per reported match. - Space: O(P) nodes (the code stores a dict per node, so a pattern set with long shared prefixes is compact).
- z can be large: N copies of "a" against patterns a, aa, aaa, ... report on the order of N * k matches, and no algorithm that lists them all can avoid that.
Edge cases
- Duplicate patterns: both ids are reported at the same index.
- Patterns that are suffixes or prefixes of each other (he, she): handled by the output links.
- Empty text: no matches; empty pattern: rejected with
ValueError(the program builds one and prints the error), since it would match at every position. - Characters absent from the trie: the walk drops to the root and carries on.
- The code is iterative, so long patterns or texts do not hit Python's recursion limit.
Common mistakes
- Building the failure links depth-first, so a parent's link is not ready when a child needs it.
- Reporting only the node's own pattern and forgetting the out_link chain, which loses every pattern nested inside a longer one.
- Falling back with
while ch not in next[node]without stopping at the root, which loops forever. - Mixing up the start index and end index when reporting.
Running the code
python ac.py
Save the listing as ac.py. It uses only the standard library.
Explain the rolling-hash technique used in Rabin-Karp for substring search. Describe how to compute an initial hash and update it in O(1) as the window slides. Using base=256 and modulus=101, outline the hash computations for pattern 'abc' and text 'zabcp'. Explain how collisions arise and how to handle false positives in practice.
Sample Answer
The idea
Comparing a pattern with every window of the text costs m characters per window. A rolling hash replaces the comparison with a number. Treat a string as digits of a number in some base b and reduce it modulo a modulus q (a prime, or at least a number with no small factors, so the remainders spread evenly) to keep it small. Two equal strings always have equal hashes, so windows with a different hash can be skipped at once. Only when hashes are equal do you compare the characters, because two different strings can share a hash (a collision).
The "rolling" part: when the window slides one place right, the new hash comes from the old one in O(1), without rereading the window.
A tiny instance first
Take base 10 and the window 345 (digits 3, 4, 5). Its value is 3*100 + 4*10 + 5 = 345. Slide one place right to 456: drop the 3 (subtract 3*100), shift everything left (multiply by 10), and add the new digit 6. That is (345 - 300)*10 + 6 = 456. Rabin-Karp does exactly this, with the base 256 and a remainder after every step.
Definitions and the O(1) update
For a window s[0..m-1]:
Computing it by Horner's rule (evaluate the sum left to right, multiplying the running total by the base and adding the next character, so one multiply and one add per character): h = (h * b + ord(c)) % q, starting from 0.
When the window drops its leading character out and gains inc:
b^(m-1) mod q (the weight of the leading character) is computed once before the loop.
Worked computation: base 256, modulus 101, pattern abc, text zabcp
The characters have codes a=97, b=98, c=99, p=112, z=122, and 256^2 mod 101 = 88 is the leading weight (m = 3).
- Pattern:
((97*256 + 98)*256 + 99) = 6382179, and6382179 mod 101 = 90(since 101 * 63189 = 6382089 and the remainder is 90). - Window
zab:((122*256 + 97)*256 + 98) = 8020322, and8020322 mod 101 = 13. - Rolling from
zabtoabc:((13 - 122*88)*256 + 99) = -2744989, and a modulus that returns a non-negative result (Python's%does) gives 90, matching the pattern's 90. Only window 1 has hash 90, so it is the only one compared character by character: one confirmed match at index 1. - Rolling from
abctobcp:((90 - 97*88)*256 + 112) = -2162064, and the remainder is 43, which differs from 90, so window 2 is skipped without any character comparison.
BASE, MOD = 256, 101
def poly_hash(s: str) -> int:
h = 0
for ch in s:
h = (h * BASE + ord(ch)) % MOD
return h
def rabin_karp(text: str, pattern: str, verbose: bool = False):
n, m = len(text), len(pattern)
if m == 0 or m > n:
return [], 0
high = pow(BASE, m - 1, MOD) # weight of the leading character
target = poly_hash(pattern)
h = poly_hash(text[:m])
hits, false_pos = [], 0
for i in range(n - m + 1):
if verbose:
print(f" window {i}: {text[i:i + m]!r} hash={h} (target {target})")
if h == target:
if text[i:i + m] == pattern:
hits.append(i)
else:
false_pos += 1
if i + m < n:
h = ((h - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
return hits, false_pos
print("ord a,b,c =", ord("a"), ord("b"), ord("c"), " 256^2 mod 101 =", pow(256, 2, 101))
print("hash('abc') =", poly_hash("abc"))
print(f" ((97*256 + 98)*256 + 99) = {(97 * 256 + 98) * 256 + 99}, mod 101 = {((97 * 256 + 98) * 256 + 99) % 101}")
high = pow(BASE, 2, MOD)
old = poly_hash("zab")
raw = (old - ord("z") * high) * BASE + ord("c")
print(f"roll 'zab' -> 'abc': (({old} - {ord('z')}*{high})*256 + {ord('c')}) = {raw}, mod 101 = {raw % MOD}")
zab = (ord("z") * 256 + ord("a")) * 256 + ord("b")
print(f"hash('zab') = (({ord('z')}*256 + {ord('a')})*256 + {ord('b')}) = {zab}, mod 101 = {zab % MOD}")
old = poly_hash("abc")
raw = (old - ord("a") * high) * BASE + ord("p")
print(f"roll 'abc' -> 'bcp': (({old} - {ord('a')}*{high})*256 + {ord('p')}) = {raw}, mod 101 = {raw % MOD}")
print("search 'abc' in 'zabcp':")
print(rabin_karp("zabcp", "abc", verbose=True))
# find a different three-letter lowercase string with the same hash as 'abc'
target = poly_hash("abc")
import itertools
collisions = [a + b + c for a, b, c in itertools.product("abcdefghijklmnopqrstuvwxyz", repeat=3)
if poly_hash(a + b + c) == target and a + b + c != "abc"]
print("lowercase 3-letter strings colliding with 'abc':", len(collisions), "first:", collisions[:3])
c = collisions[0]
print(f"search 'abc' in 'zz{c}zz':", rabin_karp("zz" + c + "zz", "abc"))
Output:
ord a,b,c = 97 98 99 256^2 mod 101 = 88
hash('abc') = 90
((97*256 + 98)*256 + 99) = 6382179, mod 101 = 90
roll 'zab' -> 'abc': ((13 - 122*88)*256 + 99) = -2744989, mod 101 = 90
hash('zab') = ((122*256 + 97)*256 + 98) = 8020322, mod 101 = 13
roll 'abc' -> 'bcp': ((90 - 97*88)*256 + 112) = -2162064, mod 101 = 43
search 'abc' in 'zabcp':
window 0: 'zab' hash=13 (target 90)
window 1: 'abc' hash=90 (target 90)
window 2: 'bcp' hash=43 (target 90)
([1], 0)
lowercase 3-letter strings colliding with 'abc': 172 first: ['akv', 'amo', 'aoh']
search 'abc' in 'zzakvzz': ([], 1)
How collisions arise, and how to handle them
There are only 101 possible hash values, but 26^3 = 17,576 lowercase three-letter strings, so by the pigeonhole principle (more items than boxes forces two items into one box) many strings must share a hash. The run lists 172 other lowercase strings with hash 90; the first is akv. Searching abc in zzakvzz gets a hash hit at index 2, the character comparison rejects it, and the function counts it as 1 false positive. The matched answer is therefore [].
Practical handling. Item 1 is the one that guarantees a correct answer; items 2 to 5 only make wasted verifications rare.
- Always verify on a hash hit (compare the m characters). With this, collisions can only cost time, never produce a wrong answer.
- Use a large modulus. A small q like 101 is only for hand arithmetic. With a prime q around 10^9 or larger, the chance that two distinct strings collide is small (roughly 1 in q for strings that look unrelated).
- Pick the base at random at startup. For a random base and prime q, two distinct strings of length m collide with probability at most (m-1)/q, because two strings collide exactly when their difference, viewed as a polynomial in the base, evaluates to 0 mod q. That difference is not the zero polynomial (the strings differ somewhere) and has degree below m. A nonzero polynomial of degree d has at most d roots modulo a prime, just as
x^2 - 5x + 6has only the roots 2 and 3, so at most m-1 of the q possible bases make the strings collide, and a random base hits one with probability at most (m-1)/q. A fixed, known base and modulus lets an adversary (someone who chooses the input to hurt the program) build many colliding strings and force the O(n*m) case. - Optionally use two independent moduli (double hashing: keep two hashes per window with different moduli), requiring both to agree before verifying.
- The base should be at least the alphabet size; here 256 mod 101 = 54, so with q = 101 the effective base is 54, one more reason to use a larger q.
Complexity
- Expected time O(n + m): O(m) to hash the pattern and first window, O(1) per slide, and an O(m) verification only on a hash hit, which happens for true matches and rarely for false ones.
- Worst case O(n*m): if many windows collide (adversarial input, or tiny q) or the text is
aaaa...and the patternaaa...a(every window is a true match and verified). - Space O(1) beyond the output.
Common mistakes
- Forgetting to subtract the leading character before multiplying by the base.
- A negative intermediate value: in languages whose
%keeps the sign of the dividend (C, C++, Java, JavaScript) the update can end negative. Addingqonce is not enough, becauseord(out) * highcan be many timesq. Reduce that product moduloqfirst, then addq, then take the remainder. The block below emulates that remainder for the step fromzabtoabc(correct hash 90).
import math
def c_mod(a: int, q: int) -> int:
# remainder as C, C++, Java and JavaScript compute it: the sign follows the dividend
return int(math.fmod(a, q))
h, out, high, inc, q = 13, 122, 88, 99, 101 # roll 'zab' -> 'abc'
print("add q once: ", c_mod((h + q - out * high) * 256 + inc, q))
print("reduce product first:", c_mod((h + q - (out * high) % q) * 256 + inc, q))
Output:
add q once: -11
reduce product first: 90
- Skipping the verification step.
- Using the same hash for the pattern and the windows with different bases or orders of characters.
Running the code
python rolling_hash.py
Python 3.12, standard library only.
Implement the KMP string search algorithm in Python: def kmp_search(text: str, pattern: str) -> List[int]. Return all starting indices where the pattern appears in the text in O(n+m) time. Include computation of the prefix-function, handle empty-pattern behavior, and explain complexity.
Sample Answer
The idea
Naive search restarts after every mismatch. KMP keeps a counter j, the number of pattern characters currently matched, and on a mismatch falls back to the next-best partial match using the prefix function pi. pi[i] is the length of the longest proper border of pattern[:i+1] (a border is a prefix that is also a suffix). The text index only moves forward, which is what makes the whole search linear.
For aabaa, the border lengths are: a has none (0), aa has a (1), aab has none (0), aaba has a (1), and aabaa has aa (2). That gives pi = [0, 1, 0, 1, 2]. The next section builds it one cell at a time.
Approach
- Build
pifor the pattern (O(m)). - For each text character
c: whilej > 0andcdiffers frompattern[j], setj = pi[j-1]. Then, ifc == pattern[j], incrementj. - When
j == m, recordi - m + 1, then setj = pi[j-1](not 0) so overlapping matches are still found. - Handle the special cases first: an empty pattern, and a pattern longer than the text.
Building pi by hand
pi is built with the same trick as the search: the pattern is searched against itself. Keep k, the length of the border of the prefix seen so far, and look at the next character p[i]:
- If
p[i] == p[k], the border grows by one:k += 1. - If not, the current border (the first
kcharacters of the pattern, which also end at positioni - 1) cannot be extended byp[i], so try a shorter border. The shorter candidates are exactly the borders of the border. Because the lastkcharacters just read equalp[:k], a border of those characters is also a border ofp[:k], andpi[k-1]is the longest of those. Sok = pi[k-1]jumps straight to the next-longest candidate, and no shorter-but-valid candidate is skipped, since any candidate longer thanpi[k-1]and shorter thankwould contradictpi[k-1]being the longest border ofp[:k]. - If
kreaches 0 andp[i] != p[0], thenpi[i] = 0.
For aabaa the run below shows each step. At i=2, b differs from p[1] = a, so k falls from 1 to pi[0] = 0 and pi[2] = 0. At i=3, a == p[0], so k = 1. At i=4, a == p[1], so k = 2.
The search loop applies the same rule to the text, with j playing the role of k.
Code
import random
from typing import List
def prefix_function(p: str) -> List[int]:
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def prefix_function_traced(p: str) -> List[int]:
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
print(f" i={i} {p[i]!r} != p[{k}]={p[k]!r}: k {k} -> {pi[k - 1]}")
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
print(f" i={i} {p[i]!r}: pi[{i}]={k} (prefix {p[:k]!r} = suffix {p[i - k + 1:i + 1]!r})")
return pi
def kmp_search(text: str, pattern: str) -> List[int]:
n, m = len(text), len(pattern)
if m == 0:
return list(range(n + 1))
if m > n:
return []
pi = prefix_function(pattern)
hits, j = [], 0 # j = how many pattern chars currently match
for i, c in enumerate(text):
while j > 0 and c != pattern[j]:
j = pi[j - 1]
if c == pattern[j]:
j += 1
if j == m:
hits.append(i - m + 1)
j = pi[j - 1] # keep the longest border so overlapping matches are found
return hits
def kmp_search_traced(text: str, pattern: str) -> List[int]:
pi = prefix_function(pattern)
hits, j = [], 0
for i, c in enumerate(text):
while j > 0 and c != pattern[j]:
print(f" i={i} {c!r} != pattern[{j}]={pattern[j]!r}: j {j} -> {pi[j - 1]}")
j = pi[j - 1]
if c == pattern[j]:
j += 1
line = f" i={i} {c!r}: j={j}"
if j == len(pattern):
hits.append(i - len(pattern) + 1)
j = pi[j - 1]
line += f" -> MATCH at {hits[-1]}, j reset to {j}"
print(line)
return hits
def text_comparisons(text: str, pattern: str) -> int:
pi = prefix_function(pattern)
j = count = 0
for c in text:
while j > 0 and c != pattern[j]:
count += 1
j = pi[j - 1]
count += 1
if c == pattern[j]:
j += 1
if j == len(pattern):
j = pi[j - 1]
return count
print("building pi('aabaa'), pi[0] = 0:")
print("pi('aabaa') =", prefix_function_traced("aabaa"))
print("trace of 'aabaa' in 'aabaabaaa':")
print(kmp_search_traced("aabaabaaa", "aabaa"))
print(kmp_search("ababa", "aba"), kmp_search("abc", ""), kmp_search("abc", "abcd"))
for n in (1000, 2000, 4000):
c = text_comparisons("a" * n, "a" * 99 + "b")
print(f"n={n}: character comparisons={c}, 2n={2 * n}")
random.seed(11)
for _ in range(2000):
t = "".join(random.choice("ab") for _ in range(random.randint(0, 14)))
p = "".join(random.choice("ab") for _ in range(random.randint(0, 6)))
expected = [i for i in range(len(t) - len(p) + 1) if t.startswith(p, i)]
assert kmp_search(t, p) == expected, (t, p)
print("2000 random cases match str.startswith scan")
Output:
building pi('aabaa'), pi[0] = 0:
i=1 'a': pi[1]=1 (prefix 'a' = suffix 'a')
i=2 'b' != p[1]='a': k 1 -> 0
i=2 'b': pi[2]=0 (prefix '' = suffix '')
i=3 'a': pi[3]=1 (prefix 'a' = suffix 'a')
i=4 'a': pi[4]=2 (prefix 'aa' = suffix 'aa')
pi('aabaa') = [0, 1, 0, 1, 2]
trace of 'aabaa' in 'aabaabaaa':
i=0 'a': j=1
i=1 'a': j=2
i=2 'b': j=3
i=3 'a': j=4
i=4 'a': j=5 -> MATCH at 0, j reset to 2
i=5 'b': j=3
i=6 'a': j=4
i=7 'a': j=5 -> MATCH at 3, j reset to 2
i=8 'a' != pattern[2]='b': j 2 -> 1
i=8 'a': j=2
[0, 3]
[0, 2] [0, 1, 2, 3] []
n=1000: character comparisons=1901, 2n=2000
n=2000: character comparisons=3901, 2n=4000
n=4000: character comparisons=7901, 2n=8000
2000 random cases match str.startswith scan
Worked trace: aabaa in aabaabaaa
The printed table shows pi('aabaa') = [0, 1, 0, 1, 2]. The first five characters match and give a hit at 0. The code then sets j = pi[4] = 2, because the last two matched characters aa are also the pattern's first two, and continues with b, a, a, producing the overlapping hit at 3 without looking back at the text. At the last character, a differs from pattern[2] = b, so j falls from 2 to pi[1] = 1, then a matches pattern[1], leaving j = 2. Result: [0, 3].
Why the search is O(n + m)
j goes up by at most 1 per text character, so over the whole run it rises at most n times. Every fallback lowers it, so there can be at most n fallbacks in total, even though one character may trigger several. The loop therefore does at most n comparisons that advance plus n that fall back. The measurement above, taken on text aaaa...a with pattern aaa...ab (99 a's then b), shows character comparisons of 1,901, 3,901 and 7,901 for n = 1,000, 2,000 and 4,000, always under 2n. Building pi is O(m) by the same argument. Space is O(m) for pi, plus the output list.
Edge cases
- Empty pattern: returns
[0, 1, ..., n](every gap), consistent withstr.find(""). State the convention. - Pattern longer than text: returns
[]immediately (also avoids a uselesspibuild). - Overlapping matches:
ababa/abagives[0, 2]. If the code resetj = 0after a match, the second hit would be lost. Onaabaabaaawith patternaabaathat variant reports only[0]and misses the match at 3. - Pattern equal to text, single-character pattern and repeated characters (
aaaa) all work, since the same loop handles them. - Unicode: indexing is by Python code point, so results are code point offsets, not byte offsets.
Common mistakes
ifinstead ofwhilein the fallback loop.- Reading
pattern[j]whenj == m(IndexError); resettingjright after a match prevents it. - Using
pi[j]instead ofpi[j-1]. - Building
pifor the single stringpattern + '#' + text, a well-known alternative way to search. Every value ofpithat equalslen(pattern)marks a match ending there, and the#separator stops any border from running past the pattern, so it must not appear in either string. The shipped code uses the two-pass search instead, which needs no separator.
The function was checked against a str.startswith scan on 2,000 random binary strings (final printed line).
Running the code
python kmp_search.py
Python 3.12, standard library only.
Unlock Full Question Bank
Get access to all 18 String Algorithms and Pattern Matching interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.