String algorithms
Text is everywhere an engineer works — logs, tokenizer input, DNA, code search, grep. The naive "slide the pattern and compare" search is O(n·m) and quietly quadratic on adversarial input. This lesson builds the linear-time alternatives from scratch: KMP and its failure function, Rabin-Karp’s rolling hash, the Z-algorithm, tries for searching many patterns at once, and the suffix-array + LCP structures that power substring queries. Every algorithm is runnable and its complexity is stated without rounding down.
Learning objectives
- Explain why naive search is O(n·m) and construct the input that makes it quadratic.
- Build KMP’s failure function and search in O(n+m) with no backtracking in the text.
- Implement Rabin-Karp’s rolling hash and know why verification is mandatory.
- Compute the Z-array in linear time and use it for pattern matching.
- Use a trie for multi-pattern membership and prefix queries.
- Reason about suffix arrays + LCP and the substring problems they solve.
1 · Naive matching and why it hurts
Here's a bug that once cost a team a very bad afternoon. Someone wrote a log scanner that looked for a marker string in each line — plain marker in line, the most natural thing in the world. It flew through the test fixtures. Then a customer streamed in a batch of machine-generated logs padded with long runs of the same character, and the same innocent scan started chewing through CPU as if it had hit an infinite loop. Nothing had changed except the shape of the input. That is the whole story of this chapter: for text, the naive approach is fine right up until an adversary — or an unlucky data source — feeds it the one input it was never designed for.
Think of searching for a word on a printed page by placing a stencil of the word over the text and checking letter by letter. If the first letter doesn't line up, you slide the stencil one position right and start over. On ordinary prose that works beautifully, because a mismatch usually shows up on the very first letter and you move on instantly. The pain only appears when the text keeps almost matching: you compare nearly the whole word, fail on the last letter, slide by one, and re-compare almost the whole word again — over and over, throwing away everything you just learned.
The common mistake is to reason about performance from the average case and forget the worst. Naive matching is close to O(n) on random text, so it feels linear, and that false confidence is exactly what ships it to production. The precise cost is O(n·m) for text length n and pattern length m, and there really is input that hits it: repeated characters plus a pattern that differs only at its end. Every linear-time algorithm in this lesson is an answer to a single question — how do we avoid re-examining text we have already matched? — so keep that waste in mind; it is the thing each trick eliminates.
The obvious algorithm slides the pattern across the text and compares character by character. It is correct and simple, and for random text it is nearly linear. The trap is adversarial input: a text of repeated as and a pattern like aaaa…ab forces every window to re-compare almost the whole pattern before failing on the last char — O(n·m). The linear algorithms all attack the same waste: never re-examine text you have already matched.
Read top-to-bottom: each row is the pattern laid over the text one position further right than the row above it.
- Each row is one window — the pattern aligned at a start position in the text. The window slides right by exactly one character on every failed attempt.
- The amber cells are characters that matched and got compared; the red cell is the single mismatch at the end that forces a shift. Notice the amber run is nearly the full pattern every time.
- The bottom red bar is the payoff: because ~n windows each re-compare ~m characters, the wasted work multiplies to O(n·m) — the quadratic blow-up on repetitive input.
In short: The naive scan re-reads text it already matched in every window; on aaaa…b that repetition turns a "linear-feeling" loop into an n×m quadratic.
def naive_search(text, pattern):
"""Slide the pattern over the text, compare char by char.
Worst case O(n * m): think text='aaaa...a', pattern='aaa...ab'."""
n, m = len(text), len(pattern)
hits = []
comparisons = 0
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
comparisons += 1
j += 1
if j == m:
hits.append(i)
return hits, comparisons
# The adversarial case that makes naive search quadratic:
text = "a" * 20 + "b"
pat = "a" * 5 + "b"
hits, comps = naive_search(text, pat)
print("match at :", hits) # [15]
print("comparisons :", comps) # many — most windows re-scan the same 'a'smatch at : [15]
comparisons : 812 · KMP and the failure function
Picture the naive scanner failing on the string abcabcx against the text abcabcabcx. You match abcabc, hit a mismatch, and your instinct — the naive instinct — is to throw away all six matched characters, slide the pattern one step, and start comparing from scratch. But stop and look at what you already know: the last three characters you matched, abc, are the same as the pattern's first three characters. You have already read them. Re-reading them is pure waste. KMP is the algorithm that refuses to waste them.
The everyday analogy is memorising a phone number as you dial. If you misdial near the end, you don't re-key the whole number — you back up to the last digit you're still sure of and continue from there. KMP does exactly this with the pattern: on a mismatch it doesn't reset to zero, it falls back to the longest chunk of the pattern it has already confirmed and resumes. The crucial payoff is that the pointer walking through the text never moves backward — it only ever goes forward, one character at a time, which is why the search is honestly linear.
All of that cleverness lives in one precomputed table, and the name trips people up, so name the mistake up front: the "failure function" is not a table of where you failed — it is a table of how much you get to keep when you fail. For each position it records the length of the longest proper prefix of the pattern that is also a suffix ending there (a "border"). When a mismatch happens at pattern position k, that border length tells you the pattern already lines up for fail[k-1] characters, so you jump straight there instead of re-scanning. Building this table is O(m), the search itself is O(n), and the two together give the headline O(n+m) that beats the naive O(n·m) on every input, adversarial or not.
Knuth-Morris-Pratt precomputes a failure function (prefix function) over the pattern: fail[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix. On a mismatch, instead of shifting by one and re-scanning, KMP jumps the pattern forward using this border — the text pointer never moves backward. Building the failure array is O(m); the search is O(n); total O(n+m).
Follow the four boxes left-to-right along the arrows — it is the KMP search loop drawn as a pipeline, one box per stage.
- The first blue box ("read text char · never backtrack") is the invariant that makes KMP linear: the text pointer only ever moves forward, one character at a time.
- The amber box ("mismatch? · reuse border") flowing into the purple box ("k = fail[k-1] · shift pattern") is the trick — on a mismatch you don't reset to zero, you consult the failure array and jump the pattern pointer
kback to the longest border already matched. - The green box on the right ("k == m → match · record hit") is the payoff: when the pattern pointer reaches the pattern's length
m, a full occurrence has been found and is recorded before the loop rolls on.
In short: The text pointer marches forward and never backtracks; only the pattern pointer k slides back via fail[k-1] — which is exactly what turns naive O(n·m) into O(n+m).
def build_failure(pattern):
"""Prefix-function (a.k.a. failure/LPS array). fail[i] = length of the
longest proper prefix of pattern[:i+1] that is also a suffix of it."""
m = len(pattern)
fail = [0] * m
k = 0 # length of current prefix-suffix
for i in range(1, m):
while k > 0 and pattern[i] != pattern[k]:
k = fail[k - 1] # fall back, never re-scan from 0
if pattern[i] == pattern[k]:
k += 1
fail[i] = k
return fail
def kmp_search(text, pattern):
"""Knuth-Morris-Pratt: O(n + m). On a mismatch, the failure function tells
us how far the pattern can shift without re-examining matched text."""
if not pattern:
return list(range(len(text) + 1))
fail = build_failure(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = fail[k - 1] # reuse the border, no backtrack in text
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = fail[k - 1] # keep searching for overlaps
return hits
print("failure(ababaca):", build_failure("ababaca")) # [0,0,1,2,3,0,1]
print("hits:", kmp_search("abababababa", "aba")) # [0,2,4,6,8]failure(ababaca): [0, 0, 1, 2, 3, 0, 1]
hits: [0, 2, 4, 6, 8]fail. Reading it: at ababa, fail = 3 means the prefix aba is also a suffix, so after a mismatch you can resume as if you had already matched those 3 characters — no re-reading.3 · Rabin-Karp — rolling hash
Imagine you're a bouncer with a guest list of a thousand names, and everyone walking in has an eight-letter name. Comparing each arrival against all thousand names, letter by letter, is exhausting. So instead you memorise a single number for each name on the list — a fingerprint. When someone arrives you compute their fingerprint and glance at your set of allowed fingerprints; only if it matches do you bother to read their actual name. Rabin-Karp is that bouncer, and the fingerprint is a hash.
The genius of it is the rolling part, and it's worth slowing down on. A naive fingerprint of every text window would cost O(m) to compute per window — no better than naive matching. But a window and the next window overlap in all but two characters, so instead of recomputing from scratch you update: subtract the contribution of the character that just left the window on the left, shift, and add the character that just entered on the right. That update is O(1), like an odometer rolling one digit — the number changes, but you didn't re-read the whole thing. Roll it across the text and you've fingerprinted every window in linear total time.
Now the trap, and it is the mistake that separates a correct implementation from a subtly broken one: hashes collide. Two different strings can produce the same fingerprint, so a matching hash means "probably a match," never "definitely a match." You must verify the actual characters on a hash hit. Skip that verification and you have quietly turned a deterministic algorithm into a probabilistic one that an attacker can fool with crafted collisions. With verification, the average cost is O(n+m); the worst case degrades to O(n·m) only if nearly every window collides. Where Rabin-Karp truly earns its place is multi-pattern search (hash a whole banned-word list into one set and roll a single window past it) and 2-D matching — jobs where standing up one KMP automaton per pattern would be clumsy.
Rabin-Karp hashes the pattern once, then rolls a hash over each text window: when the window shifts by one, subtract the leaving character’s contribution and add the entering one, all in O(1). A window is a candidate only when its hash equals the pattern’s hash — but hashes collide, so you must verify the actual characters on a hit. Average O(n+m); worst case O(n·m) if every window collides. Its real strength is multi-pattern and 2-D search.
Read the left half first (how the hash updates), then follow the arrow across the dashed divider to the right half (what you do with a hash hit).
- The row of cells is the current window; the red cell on the left is the character leaving as the window slides, the green cell on the right is the character entering. The purple box shows the O(1) update — subtract the leaver, shift, add the newcomer.
- The right column is the decision: equal hashes send you down to the verify box, and only a real character-by-character match becomes a green true match.
- The red line at the bottom is the trap this picture proves: hashes can be equal while the strings differ (a collision), so skipping the verify step reports a false match.
In short: The rolling hash makes each window O(1) to score, but the hash only nominates candidates — the verify step is mandatory, not optional.
def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
"""Rolling-hash search. Hash the window in O(1) per shift; verify on a hash
hit to eliminate collisions. Average O(n + m); worst case O(n * m)."""
n, m = len(text), len(pattern)
if m == 0 or m > n:
return []
high = pow(base, m - 1, mod) # value of the leading digit's place
ph = th = 0
for i in range(m): # hash the pattern and first window
ph = (ph * base + ord(pattern[i])) % mod
th = (th * base + ord(text[i])) % mod
hits = []
for i in range(n - m + 1):
if ph == th and text[i:i + m] == pattern: # verify to reject collisions
hits.append(i)
if i < n - m: # roll: drop text[i], add text[i+m]
th = (th - ord(text[i]) * high) % mod
th = (th * base + ord(text[i + m])) % mod
th %= mod
return hits
print(rabin_karp("abracadabra", "abra")) # [0, 7]
print(rabin_karp("aaaaa", "aa")) # [0, 1, 2, 3][0, 7]
[0, 1, 2, 3]text[i:i+m] == pattern verification turns a correct algorithm into a probabilistic one. On adversarial input crafted to collide, an unverified Rabin-Karp reports false matches. Always confirm on a hash hit.4 · The Z-algorithm
KMP is powerful but its failure function makes a lot of people's eyes glaze over — the "longest proper prefix that is also a suffix" definition is precise but hard to see. The Z-algorithm solves the same linear-time matching problem with an idea that's far easier to picture, and once it clicks you'll reach for it whenever KMP feels fiddly. So if section 2 left you memorising rather than understanding, this section is the friendlier door into the same room.
Here's the picture. Lay a string down and, standing at each position i, ask a simple question: "starting right here, how many characters match the very beginning of the string?" That count is Z[i]. Position 0 is the whole string (it matches itself), and everywhere else you get the length of the run that echoes the opening of the string. It's like walking along a wallpaper pattern and, at every step, noting how long the design keeps agreeing with the pattern's start before it diverges.
Computed naively, answering that question at every position is O(n²) — you'd re-scan the same characters constantly, the exact waste this whole chapter fights. The trick that makes it O(n) is to remember the rightmost match you've already discovered — a window nicknamed the "Z-box." Whenever a new position falls inside that box, you already know what the string looks like there (it mirrors the prefix), so you can copy a previously computed Z-value instead of re-comparing, and only scan fresh characters when you run off the edge of the box. The common misstep is forgetting to slide the box forward after extending a match; without that, the reuse breaks and you're back to quadratic. To search for a pattern you glue pattern + separator + text together and compute one Z-array: any position whose Z-value equals len(pattern) is a full occurrence. One array, one pass, O(n+m) — conceptually simpler than KMP for many problems.
The Z-array gives, for each position i, the length of the longest substring starting at i that matches a prefix of the string. It is computed in O(n) by maintaining the rightmost matched window (the "Z-box") and reusing previously computed values inside it. To search, concatenate pattern + separator + text; any position whose Z-value equals len(pattern) is a full match. Conceptually simpler than KMP for many problems.
pattern + sep + text, compute Z once, and every place the Z-value equals the pattern length m (the green cells) is an exact occurrence.
Read top-to-bottom: the top strip is the string you build, the middle strip is its Z-array, and the bottom box turns the array back into text positions.
- The top strip is the concatenation: the pattern, a separator character that appears nowhere else, then the text. The separator stops matches from spilling across the boundary.
- The middle strip is the Z-array over that whole string — each cell is how long the run starting there echoes the prefix (the pattern). Green cells hold the value
m, the pattern's length. - The bottom amber box is the payoff: wherever Z equals
m, the pattern reappears in full, and subtracting the pattern+separator offset (i − m − 1) gives its position in the original text.
In short: Build one string, run one linear Z-pass, and read off every position where the Z-value hits the pattern length — no separate failure table to reason about.
def z_array(s):
"""Z[i] = length of the longest substring starting at i that matches a
prefix of s. Linear O(n) using a [l, r] window of the rightmost match."""
n = len(s)
z = [0] * n
z[0] = n
l = r = 0 # current rightmost Z-box [l, r]
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l]) # reuse info inside the box
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1 # extend past the box if possible
if i + z[i] > r:
l, r = i, i + z[i] # slide the box right
return z
def z_search(text, pattern, sep="\x00"):
"""Pattern search via Z: build pattern + sep + text, then any Z value equal
to len(pattern) marks a full match. O(n + m)."""
combo = pattern + sep + text
z = z_array(combo)
m = len(pattern)
return [i - m - 1 for i in range(m + 1, len(combo)) if z[i] == m]
print("z(aabaab):", z_array("aabaab")) # [6,1,0,3,1,0]
print("hits:", z_search("aabaabaab", "aab")) # [0, 3, 6]z(aabaab): [6, 1, 0, 3, 1, 0]
hits: [0, 3, 6]| Algorithm | Preprocess | Search | Notes |
|---|---|---|---|
| Naive | — | O(n·m) | quadratic on adversarial input |
| KMP | O(m) | O(n) | no text backtrack; failure function |
| Rabin-Karp | O(m) | O(n) avg | great for multi-pattern; verify hits |
| Z-algorithm | O(n+m) | O(n+m) | one array; prefix-based |
5 · Tries for multi-pattern search
Every time your phone finishes a word before you do, a trie is probably doing the work. Type "car" and up pop "card," "care," "carpet" — instantly, out of a dictionary of a hundred thousand words. It doesn't scan the whole dictionary; that would be hopeless at every keystroke. It walks a tree where the path c → a → r leads to a single branch point, and everything below that branch is a completion. That structure — sharing the road until the words diverge — is a trie, and it's the tool for the moment you stop searching for one pattern and start searching for a whole set of them.
The name is a pun on retrieval (many people say "try" to avoid confusing it with "tree"), and the mental model is a map of shared roads. Imagine a town where every street name starts from the same central square. Names beginning "Chur-" all leave the square on the same road and only fork apart at "Church Street" versus "Churchill Avenue." A trie stores strings the same way: common prefixes share nodes, and each stored word is marked by an end-of-word flag at the node where it finishes. Because you follow the road character by character, checking membership or a prefix costs O(key length) — and here is the part that surprises people — that cost is completely independent of how many words are stored. A trie with ten words and a trie with ten million words both answer "is card in here?" in four steps.
The mistake to avoid is reaching for a trie when a plain hash set would do. If all you ever ask is "is this exact word present?", a set is simpler and lighter. The trie earns its keep the moment you need prefix questions — autocomplete, "all words starting with…", or storing a lexicon compactly by sharing prefixes. Push the idea one step further and add KMP-style failure links across the trie via a BFS, and you get Aho-Corasick: a machine that finds every pattern from a set in a single O(n) sweep of the text — the true multi-pattern generalisation of KMP, which you build in the ladder.
A trie (prefix tree) stores a set of strings so that shared prefixes share nodes. Membership and prefix queries cost O(key length), independent of how many words are stored — the reason autocomplete and dictionary lookups use them. A trie plus BFS failure links is Aho-Corasick, which searches for all patterns in a single O(n) pass (the multi-pattern generalisation of KMP — you build it in the ladder).
cat, car, card all walk c → a before forking; green nodes carry an end-of-word flag. Looking up a word follows its letters — cost is the word's length, not the dictionary's size.
Read it top-to-bottom from the root, following one letter per edge — each path spelled out from the root is a stored (or partial) word.
- The root is the empty start; every stored word leaves it on the edge of its first letter (
cfor cat/car/card,dfor dog). - Follow the edges letter by letter:
c → ais shared by cat, car and card, so those words reuse the same two nodes before they fork attversusr. That sharing is what makes a trie compact. - The green nodes are marked end-of-word:
cardcontinues pastcar's green node, which is why "car" and "card" can both be real words on the same branch. Reaching a node costs one step per letter — independent of how many words the trie holds.
In short: Walk the letters from the root; shared prefixes share nodes and green flags mark whole words — so lookup is O(word length), not O(number of words).
class Trie:
"""A prefix tree for multi-pattern membership and prefix queries.
Insert/lookup are O(key length), independent of how many words are stored."""
def __init__(self):
self.children = {}
self.is_word = False
def insert(self, word):
node = self
for ch in word:
node = node.children.setdefault(ch, Trie())
node.is_word = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s):
node = self
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
t = Trie()
for w in ["cat", "car", "card", "dog"]:
t.insert(w)
print("search 'car' :", t.search("car")) # True
print("search 'ca' :", t.search("ca")) # False (prefix, not a word)
print("prefix 'car' :", t.starts_with("car")) # True
print("prefix 'z' :", t.starts_with("z")) # Falsesearch 'car' : True
search 'ca' : False
prefix 'car' : True
prefix 'z' : False6 · Suffix arrays and LCP
All the algorithms so far preprocess the pattern and then scan the text once. That's perfect when the text changes every time. But flip the situation: what if the text is fixed — a whole book, a genome, a giant codebase — and you're going to run thousands of different searches against it? Preprocessing the pattern buys you nothing when the pattern keeps changing. The smart move is to preprocess the text once, into a structure that answers any future substring query fast. The suffix array is that structure, and it is how tools query enormous fixed texts.
The idea is disarmingly simple. Take every suffix of the string — every "tail" from each position to the end — and sort them alphabetically. You don't store the suffixes themselves (that would be quadratic space); you store their start indices in sorted order. That sorted list is the suffix array. Why does sorting help? Because once suffixes are in dictionary order, every substring you might search for is a prefix of some contiguous run of them, so you can binary-search for any pattern in O(m log n) — the same reason a physical dictionary lets you find a word fast: the sorting was done once, up front.
Sorting also places the most-similar suffixes right next to each other, and that neighbourliness is where the second structure comes in. The LCP array records the longest common prefix between each pair of adjacent sorted suffixes, and Kasai's algorithm computes it in O(n). That one extra array quietly unlocks a whole family of problems — longest repeated substring, the count of distinct substrings, longest common substring of two texts — because "how much do neighbours share?" is exactly the question those problems reduce to. One caution on complexity so you don't over-promise: the teaching build below sorts suffixes directly, which is easy to read but O(n² log n) because comparing two suffixes can itself take O(n); production builders use prefix doubling for O(n log n) or SA-IS for O(n). Learn the shape here, reach for a library at scale.
A suffix array is the sorted list of all suffix start indices of a string. Once built, you can binary-search for any substring in O(m log n). The companion LCP array (longest common prefix between adjacent sorted suffixes) is computed in O(n) by Kasai’s algorithm and unlocks a family of problems: longest repeated substring, number of distinct substrings, longest common substring of two strings. The naive build below sorts suffixes directly (great for intuition); production builders reach O(n log n) (prefix doubling) or O(n) (SA-IS).
Read down the rows: they are all six suffixes of banana, listed in sorted (dictionary) order rather than by position.
- The left column is each suffix spelled out; the SA index column is where that suffix starts in the original string — this list of indices is the suffix array (
[5,3,1,0,4,2]). - The LCP column records how many leading characters each row shares with the row directly above it. Because sorting puts similar suffixes next to each other, these neighbour-comparisons are all you need.
- The green LCP value 3 (between
anaandanana) is the largest, and the amber bar shows the payoff: that maximum is the length of the longest repeated substring,ana— found without comparing every pair.
In short: Sorting the suffixes makes substrings binary-searchable, and the largest gap-free LCP between neighbours hands you the longest repeat directly.
def suffix_array(s):
"""Build the suffix array: indices of all suffixes sorted lexicographically.
This simple version sorts suffixes directly — O(n^2 log n); good for
intuition. Production uses O(n log n) prefix-doubling or O(n) SA-IS."""
return sorted(range(len(s)), key=lambda i: s[i:])
def lcp_array(s, sa):
"""Kasai's algorithm: longest-common-prefix between adjacent suffixes in the
suffix array, in O(n). lcp[i] = LCP(sa[i-1], sa[i])."""
n = len(s)
rank = [0] * n
for i, suf in enumerate(sa):
rank[suf] = i
lcp = [0] * n
h = 0
for i in range(n):
if rank[i] > 0:
j = sa[rank[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
lcp[rank[i]] = h
if h > 0:
h -= 1 # next suffix shares all but one char
else:
h = 0
return lcp
s = "banana"
sa = suffix_array(s)
print("suffix array :", sa) # [5,3,1,0,4,2]
print("sorted suffixes :", [s[i:] for i in sa])
print("lcp array :", lcp_array(s, sa)) # [0,1,3,0,0,2]suffix array : [5, 3, 1, 0, 4, 2]
sorted suffixes : ['a', 'ana', 'anana', 'banana', 'na', 'nana']
lcp array : [0, 1, 3, 0, 0, 2]3, between ana and anana) is the length of the longest repeated substring — ana. That single fact powers plagiarism detection and de-duplication; you build it in the top rung of the ladder.7 · Edit distance — a string DP recap
Every time you fat-finger a search and the results come back anyway — "Showing results for…" — something measured how close your typo was to a real word and decided it was close enough to fix silently. That "how close are two strings" number is edit distance, and it is a different question from everything above. The pattern-matching algorithms so far all asked a yes/no question: "is this exact pattern present?" Edit distance asks a quantity: "if these two strings aren't identical, exactly how far apart are they?" That shift from exact to approximate is what powers spell-check, fuzzy search, diff, and DNA alignment.
The concrete definition: the edit distance between two strings is the minimum number of single-character insertions, deletions, and substitutions that turn one into the other. Turning kitten into sitting takes three edits (substitute k→s, substitute e→i, insert g), so their distance is 3. The reason you can't just eyeball it is that the edits interact — an early insertion shifts everything after it — so you need to consider how choices combine, which is precisely what dynamic programming is for.
This is the DP you already met in D11, so we won't re-derive it; we're revisiting it through a string lens. The mental model is a grid: rows for one string, columns for the other, and each cell holds the cheapest way to reconcile the two prefixes up to that point, built from its three neighbours (the delete, insert, and match/substitute choices). The one optimisation worth naming here is space: a full grid is O(m·n) memory, but because each row only ever looks at the row directly above it, you can keep just two rows and drop the rest — the same O(m·n) time but only O(n) space. The common mistake is to build the whole matrix out of habit when all you need is the final distance; the two-row form below is the one to reach for.
Pattern matching asks "is P here exactly?"; edit distance asks "how different are two strings?" — the minimum insertions, deletions, and substitutions to turn one into the other. It is the dynamic program from D11, shown here in its space-optimised two-row form. It underlies fuzzy search, spell-check, diff tools, and DNA alignment. O(m·n) time, O(n) space.
Read the top block first (how one cell is computed), then the bottom block (why only two rows are needed).
- The 2×2 grid shows the current cell (
cur, purple) and its three contributing neighbours. The three blue arrows are the three edit choices flowing into it. - The diagonal is match-or-substitute (add 1 only if the characters differ); up is a deletion and left is an insertion, each costing 1. The cell takes the minimum of those three — the cheapest way to line up the prefixes so far.
- The green/amber row pair at the bottom is the space trick: since a cell only ever looks one row up, you discard everything older and keep just the prev and cur rows — dropping memory from O(m·n) to O(n). The final answer is the last cell of the last row.
In short: Fill each cell from its diagonal/up/left neighbours and take the minimum; because only the previous row matters, two rows of memory suffice.
def edit_distance(a, b):
"""Levenshtein distance (cross-link ds11 · DP). Minimum insert/delete/
substitute operations to turn a into b. O(len(a) * len(b))."""
m, n = len(a), len(b)
prev = list(range(n + 1)) # dp row for empty prefix of a
for i in range(1, m + 1):
cur = [i] + [0] * n
for j in range(1, n + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
cur[j] = min(prev[j] + 1, # delete from a
cur[j - 1] + 1, # insert into a
prev[j - 1] + cost) # match / substitute
prev = cur
return prev[n]
print(edit_distance("kitten", "sitting")) # 3
print(edit_distance("flaw", "lawn")) # 23
2✓ Checkpoint — you can move on when you can…
- Construct a text/pattern pair that makes naive search do Θ(n·m) work.
- Read a failure-function array and state what each entry means.
- Explain why Rabin-Karp must verify a hash hit and when its worst case triggers.
- Compute a small Z-array by hand and use it to locate a pattern.
- Give one problem where a trie beats a hash set, and why.
- Use an LCP array to find the longest repeated substring of a string.
KMP and Rabin-Karp both search in O(n) on typical input. Name one concrete situation where you would specifically choose Rabin-Karp.
Show answer
You are told a pattern P of length m has failure value fail[m-1] = k with k > 0 and m % (m - k) == 0. What does this tell you about P?
Show answer
P is periodic with period m - k: it is some string of length m - k repeated exactly m / (m - k) times. The border (prefix = suffix) of length k overlaps itself, which is only possible when the string is a whole number of copies of its period. You use this in the 'smallest period' ladder exercise.🪜 Practice ladder beginner → industry
Six graded exercises, easy to real-world. Try each before opening its solution.
Context: The simplest correctness baseline before optimising: counting substring occurrences, including overlapping ones (which str.count does not do).
Your task: Return both the count and the positions of every (possibly overlapping) occurrence of a pattern in a text.
Requirements:
- Scan every start position and compare the slice
- Count overlapping matches (e.g. 'aa' in 'aaaa' → 3)
- Return the positions as well as the count
- Verify on the overlapping example
💡 Hint: Step the start index by 1, not by the pattern length — that is what keeps overlaps.
Show solution
def count_occurrences(text, pattern):
"""Count (possibly overlapping) occurrences with a naive scan, returning the
positions too. Baseline before the linear algorithms."""
n, m = len(text), len(pattern)
positions = []
for i in range(n - m + 1):
if text[i:i + m] == pattern:
positions.append(i)
return len(positions), positions
count, pos = count_occurrences("aaaa", "aa")
print("count :", count) # 3 (overlaps counted)
print("positions :", pos) # [0, 1, 2]Context: The 'border' of a string (a proper prefix that is also a suffix) is the single value KMP is built on; computing it directly cements the idea.
Your task: For several strings, report the length and text of the longest proper prefix that is also a suffix.
Requirements:
- Reuse the KMP failure-function build
- The answer is the last value of the failure array
- Show it on a periodic string, a repeat, and a border-free string
- Return both the length and the border substring
💡 Hint: fail[-1] already holds the longest-border length — no extra pass needed.
Show solution
def build_failure(pattern):
m = len(pattern)
fail = [0] * m
k = 0
for i in range(1, m):
while k > 0 and pattern[i] != pattern[k]:
k = fail[k - 1]
if pattern[i] == pattern[k]:
k += 1
fail[i] = k
return fail
def longest_repeated_border(pattern):
"""The failure function's last value is the length of the longest proper
prefix that is also a suffix — the 'border' used to build periodic strings."""
fail = build_failure(pattern)
k = fail[-1]
return k, pattern[:k]
for w in ["ababab", "abcabc", "aaaa", "abcd"]:
length, border = longest_repeated_border(w)
print(f"{w:8} border len={length} border={border!r}")Context: Detecting the shortest repeating unit of a string is used in compression and in spotting periodic signals in logs; it falls straight out of KMP.
Your task: Given a string, return its smallest period and the repeating unit (the whole string if it does not repeat).
Requirements:
- Build the failure function
- Candidate period is
n - fail[-1] - It is a true period only if
n % period == 0 - Fall back to the whole string when there is no repetition
💡 Hint: A string of length n has period n - fail[n-1] exactly when that value divides n evenly.
Show solution
def smallest_period(s):
"""Shortest string whose repetition builds s. Uses KMP's failure function:
if n % (n - fail[-1]) == 0, the period is (n - fail[-1])."""
n = len(s)
fail = [0] * n
k = 0
for i in range(1, n):
while k > 0 and s[i] != s[k]:
k = fail[k - 1]
if s[i] == s[k]:
k += 1
fail[i] = k
period = n - fail[-1]
if n % period == 0 and period != n:
return period, s[:period]
return n, s # no repetition: the whole string
print(smallest_period("abcabcabc")) # (3, 'abc')
print(smallest_period("aaaa")) # (1, 'a')
print(smallest_period("abcd")) # (4, 'abcd')Context: Searching many equal-length patterns at once (banned-word lists, signature scanning) is where rolling hashes shine over per-pattern KMP.
Your task: Search a text for many equal-length patterns in a single rolling pass and return the match positions for each.
Requirements:
- Hash all patterns into a set/dict of hash → patterns
- Roll one window hash across the text
- Verify candidates against the real characters
- Return a mapping pattern → list of positions
💡 Hint: All patterns share one length, so one window size and one rolling hash covers them all; the hash bucket narrows which patterns to verify.
Show solution
def rabin_karp_multi(text, patterns, base=256, mod=1_000_000_007):
"""Search many equal-length patterns in one pass by hashing them into a set
and rolling a single window hash over the text. Average O(n + total m)."""
if not patterns:
return {}
m = len(patterns[0])
assert all(len(p) == m for p in patterns), "all patterns must be equal length"
def h(s):
v = 0
for ch in s:
v = (v * base + ord(ch)) % mod
return v
want = {} # hash -> list of patterns
for pt in patterns:
want.setdefault(h(pt), []).append(pt)
high = pow(base, m - 1, mod)
result = {pt: [] for pt in patterns}
n = len(text)
if m > n:
return result
th = h(text[:m])
for i in range(n - m + 1):
if th in want:
window = text[i:i + m]
for pt in want[th]:
if pt == window: # verify against hash collisions
result[pt].append(i)
if i < n - m:
th = (th - ord(text[i]) * high) % mod
th = (th * base + ord(text[i + m])) % mod
th %= mod
return result
print(rabin_karp_multi("ababab", ["ab", "ba", "cd"]))Context: Aho-Corasick is the industrial multi-pattern matcher behind intrusion detection, DLP scanners and fgrep -f — a trie with KMP-style failure links.
Your task: Build an Aho-Corasick automaton from a set of patterns and report every occurrence of every pattern in one pass over the text.
Requirements:
- Build a trie of the patterns
- Set failure links with a BFS (the multi-pattern generalisation of KMP)
- Propagate output matches along failure links
- Return (position, pattern) for every match, e.g. on the classic 'ushers' / ['he','she','his','hers'] example
💡 Hint: A node’s failure link points to the longest proper suffix that is also a prefix somewhere in the trie — exactly KMP’s idea, generalised to many patterns.
Show solution
class AhoNode:
__slots__ = ("children", "fail", "out")
def __init__(self):
self.children = {}
self.fail = None
self.out = [] # patterns ending at this node
from collections import deque
def build_aho_corasick(patterns):
"""Trie + BFS failure links = search for ALL patterns simultaneously in one
O(n) pass over the text. The multi-pattern generalisation of KMP."""
root = AhoNode()
for pt in patterns:
node = root
for ch in pt:
node = node.children.setdefault(ch, AhoNode())
node.out.append(pt)
q = deque()
for child in root.children.values():
child.fail = root
q.append(child)
while q: # BFS to set failure links
node = q.popleft()
for ch, child in node.children.items():
f = node.fail
while f is not None and ch not in f.children:
f = f.fail
child.fail = f.children[ch] if f and ch in f.children else root
child.out += child.fail.out # inherit matches via failure link
q.append(child)
return root
def aho_search(text, patterns):
root = build_aho_corasick(patterns)
node = root
found = []
for i, ch in enumerate(text):
while node is not None and ch not in node.children:
node = node.fail
node = node.children[ch] if node and ch in node.children else root
for pt in node.out:
found.append((i - len(pt) + 1, pt))
return sorted(found)
print(aho_search("ushers", ["he", "she", "his", "hers"]))
# [(1, 'she'), (2, 'he'), (2, 'hers')]Context: De-duplication and near-duplicate/plagiarism detection reduce to finding the longest substring that occurs twice — the headline application of the suffix-array + LCP pair.
Your task: Return the longest substring that appears at least twice in a string.
Requirements:
- Build the suffix array and its LCP array (Kasai)
- The answer’s length is the maximum LCP value
- Recover the substring from the corresponding suffix index
- Verify on 'banana' → 'ana' and 'mississippi' → 'issi'
💡 Hint: Adjacent suffixes in sorted order share the longest prefixes, so the biggest LCP entry is the longest repeat — no pairwise comparison needed.
Show solution
def suffix_array(s):
return sorted(range(len(s)), key=lambda i: s[i:])
def lcp_array(s, sa):
n = len(s); rank = [0] * n
for i, suf in enumerate(sa):
rank[suf] = i
lcp = [0] * n; h = 0
for i in range(n):
if rank[i] > 0:
j = sa[rank[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
lcp[rank[i]] = h
if h > 0:
h -= 1
else:
h = 0
return lcp
def longest_repeated_substring(s):
"""A substring that occurs at least twice with maximum length is exactly the
maximum value in the LCP array — a classic suffix-array application used in
plagiarism detection and de-duplication."""
if len(s) < 2:
return ""
sa = suffix_array(s)
lcp = lcp_array(s, sa)
best = max(range(len(lcp)), key=lambda i: lcp[i])
length = lcp[best]
start = sa[best]
return s[start:start + length]
print(repr(longest_repeated_substring("banana"))) # 'ana'
print(repr(longest_repeated_substring("abcpqrabcxyz"))) # 'abc'
print(repr(longest_repeated_substring("mississippi"))) # 'issi