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
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.
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
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).
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
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.
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
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.
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
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).
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
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).
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
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.
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