Finding a needle, quickly
Press Ctrl+F in a document and type a word: every occurrence lights up before you have lifted your finger. A biologist asks whether a 20-letter DNA probe appears anywhere in a three-billion-letter genome. A security system scans every packet crossing a network for thousands of known attack signatures at once. A phone keyboard suggests "Kathmandu" after you have typed "Kat". A plagiarism checker compares an essay against millions of web pages.
All of these are string algorithms: algorithms whose input is text, or anything that can be written as a sequence of symbols. The obvious way to search a text is fine for a short document and painfully slow for a genome; the difference between the two is a handful of beautiful ideas that every working engineer should own. In this lesson you will meet four of them:
- Reuse what you already know (Knuth–Morris–Pratt): when a match fails part-way through, the characters you have already compared tell you where the next possible match can start.
- Compare fingerprints, not strings (Rabin–Karp): a hash of a window of text can be updated in constant time as the window slides, so most positions are rejected with one number comparison.
- Index once, search many times (tries and suffix arrays): if you will search the same collection again and again, pay once to organise it.
- Know what a character is (Unicode): before any of the above can be correct on real text, you must agree on what the symbols are.
The closely related problem of measuring how different two strings are, the edit distance, was solved in Dynamic programming; we will point back to it rather than repeat it.
Strings, patterns and borders
Definition— alphabet, string, substring
An alphabet is a finite set of symbols: , , or the code points of Unicode. A string of length is a sequence of symbols. A substring is a contiguous piece , written s[i:j] in Python. A prefix is a substring that starts at position 0; a suffix is one that ends at position .
Definition— the string-matching problem
Given a text of length and a pattern of length , find every shift with such that . Occurrences may overlap: the pattern abab occurs at shifts 0, 2 and 4 of abababab.
Definition— border, prefix function
A border of a string is a string that is both a proper prefix and a proper suffix of ("proper" means shorter than itself). The prefix function of a pattern is the array where is the length of the longest border of , the first characters.
For example, ACAAC has the borders AC and the empty string (the prefix AC equals the suffix AC; A is a prefix but the string ends in C), so its longest border has length 2. Borders are the whole secret of KMP: a border is a piece of the pattern that can slide forward and still line up with itself.
The obvious algorithm and what it forgets
The naive algorithm tries every shift: line up under at shift 0 and compare character by character until a mismatch or a full match; then move one place right and start again from the beginning of .
On ordinary prose this is fast, because a mismatch usually happens at the first or second character. But consider the text aaaa…a ( letters) and the pattern aa…ab ( copies of a and then b). At every one of the shifts, the first comparisons succeed and the last one fails, so the algorithm makes comparisons: . For a 1,000-letter pattern in a million-letter text that is about a billion comparisons.
Look closely at what the naive algorithm throws away. At shift 0 it learned that is aa…a. At shift 1 it compares , , … against a again, even though it already knows the answer. The comparisons that succeeded contain information about the text, and the naive algorithm forgets it every time it moves.
Analogy, not a formal construction
You are reading a long number aloud to a friend who is checking it against a list, and you stumble on the seventh digit. You would not go back to the beginning of the whole page; you know which digits you have already read correctly, and you would restart from the last point that could still be right. KMP formalises "the last point that could still be right".
Knuth–Morris–Pratt: never read a text character twice
Suppose we have matched the first characters of against the text, and the next text character disagrees with . Those text characters are exactly , so we know them without looking. Which shifts could still produce a match? Only shifts where some prefix of lines up with a suffix of , that is, where a border of sits under the text we just read. The longest such border gives the smallest safe shift, so we keep characters "already matched" and compare the same text character again against . If that fails too, we fall back again, to the longest border of that border, and so on, until either a comparison succeeds or .
Example— The prefix function of ACAACAC
Work left to right, keeping , the length of the longest border found so far.
| longest border | |||
|---|---|---|---|
| 0 | A | (empty) | 0 |
| 1 | AC | (empty) | 0 |
| 2 | ACA | A | 1 |
| 3 | ACAA | A | 1 |
| 4 | ACAAC | AC | 2 |
| 5 | ACAACA | ACA | 3 |
| 6 | ACAACAC | AC | 2 |
Row 3 shows a fall-back: the border A of ACA would extend to AC, but the new character is A, not C, so we fall back to the longest border of A, which is empty, and then A extends it to length 1. Row 6 is the interesting one: the border ACA would extend to ACAA, but the new character is C; the longest border of ACA is A (that is ), and A followed by C matches the pattern's AC, so .
The key fact behind the fall-back is that a border of a border is a border: if is a border of and is a border of , then is a prefix of , hence of , and a suffix of , hence of . So the borders of , longest first, are exactly , then of that, and so on down to zero. Computing is itself a matching problem, the pattern against itself, and uses the same loop.
def naive_search(text, pattern):
"""Every shift where pattern occurs in text, and the number of character comparisons."""
n, m = len(text), len(pattern)
hits, comparisons = [], 0
for s in range(n - m + 1):
j = 0
while j < m:
comparisons += 1
if text[s + j] != pattern[j]:
break
j += 1
if j == m:
hits.append(s)
return hits, comparisons
def prefix_function(p):
"""pi[i] = length of the longest proper border of p[:i+1]."""
pi = [0] * len(p)
k = 0 # length of the current border
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1] # fall back to the next shorter border
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text, pattern):
pi = prefix_function(pattern)
hits, comparisons, k = [], 0, 0 # k = how much of the pattern is matched
for i, c in enumerate(text):
while True:
comparisons += 1
if c == pattern[k]:
k += 1
break
if k == 0:
break
k = pi[k - 1]
if k == len(pattern): # a full match ending at position i
hits.append(i - k + 1)
k = pi[k - 1] # keep going: matches may overlap
return hits, comparisons
print(prefix_function("ACAACAC"))
text = "GACAACACAACACTT"
print(naive_search(text, "ACAACAC"))
print(kmp_search(text, "ACAACAC"))
# The naive algorithm's bad case: a long run of a's, and a pattern that fails only at its end.
text = "a" * 2000
pattern = "a" * 30 + "b"
print("naive:", naive_search(text, pattern)[1], "comparisons")
print("KMP: ", kmp_search(text, pattern)[1], "comparisons")Both find the overlapping matches at shifts 1 and 6 of the short text. On the bad case the naive algorithm makes comparisons and KMP fewer than . Try changing the pattern to "a" * 300 + "b": the naive count grows tenfold, KMP's does not move.
Theorem— KMP runs in linear time
The prefix function of a pattern of length is computed with at most character comparisons, and the search over a text of length makes at most . So KMP takes time and extra space, whatever the alphabet and whatever the input.
Proof
Look at the search loop and the quantity , the number of pattern characters currently matched. Each comparison either succeeds or fails. A successful comparison increases by one and moves on to the next text character, so there are at most successful comparisons. A failed comparison either ends the work on this text character (when , at most times in total) or replaces by , a strict decrease. Since starts at 0, never goes negative, and increases by at most one per text character, the total of all decreases is at most the total of all increases, which is at most . Adding up: at most successes plus at most failures, so at most comparisons. The same argument, with the pattern as its own text, bounds the prefix-function computation by . (This style of argument, charging decreases to earlier increases, is called amortised analysis.)
∎
Rabin–Karp: compare fingerprints, not strings
KMP is clever about which comparisons to make. Rabin and Karp took a different route: make each comparison cheap. Treat a window of characters as a number written in base (say , or anything larger than the alphabet) and reduce it modulo a prime :
If the hash of a window differs from the hash of the pattern, the window certainly is not the pattern. If they agree, it probably is, and we check character by character to be sure. The trick that makes this fast is that the hash rolls: sliding the window one place right removes the leading character's contribution and appends a new trailing one,
which is a constant number of arithmetic operations, however long the pattern. (If modular arithmetic is rusty, Lumenary Math's clock arithmetic lesson covers it.)
import random
def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
"""Every shift where pattern occurs, and how many hash matches turned out to be false alarms."""
n, m = len(text), len(pattern)
if m > n:
return [], 0
high = pow(base, m - 1, mod) # weight of the character that leaves the window
hp = ht = 0
for i in range(m):
hp = (hp * base + ord(pattern[i])) % mod
ht = (ht * base + ord(text[i])) % mod
hits, spurious = [], 0
for s in range(n - m + 1):
if ht == hp: # equal hashes: probably a match, so check
if text[s:s + m] == pattern:
hits.append(s)
else:
spurious += 1
if s + m < n: # roll: drop text[s], bring in text[s + m]
ht = ((ht - ord(text[s]) * high) * base + ord(text[s + m])) % mod
return hits, spurious
rng = random.Random(2026)
genome = "".join(rng.choice("ACGT") for _ in range(200_000))
probe = genome[123_456:123_468] # a 12-letter piece we know is in there
for mod in (101, 10_007, 1_000_000_007):
hits, spurious = rabin_karp(genome, probe, mod=mod)
print(f"mod {mod:>13,}: matches at {hits}, false alarms: {spurious}")With a tiny modulus the hash values collide constantly: roughly one window in shares the pattern's hash by accident, so there are about false alarms, each costing an -character check. With around there are essentially none. In expectation the running time is plus times the number of false alarms.
Theorem— False alarms are rare when the base is random
Let be a prime and choose the base uniformly at random from . For two different strings of length , the probability that is at most .
Proof
is the value at of a polynomial of degree at most with coefficients . Since and the symbols are smaller than , at least one coefficient is nonzero modulo , so it is a nonzero polynomial over the field . Such a polynomial has at most roots, so at most of the possible bases make the hashes equal.
∎
The randomness matters in adversarial settings. With a fixed, published base and modulus, someone who wants to slow your service down can construct many strings with the same hash. A random base, chosen when the program starts, takes that power away; you will see the same idea, applied to hash tables, in Randomness in algorithms.
Rabin–Karp shines where KMP is awkward. To search for many patterns of the same length, put all their hashes in a set and test each window's hash against the set in . To find a long substring that two documents share, hash every window of both. Document-fingerprinting systems for detecting copied code and text, such as the winnowing scheme of Schleimer, Wilkerson and Aiken (2003), are built on rolling hashes.
Searching many times: tries and suffix arrays
KMP and Rabin–Karp read the whole text for every query. That is optimal for one search, but if the text stays the same while the queries keep coming (a dictionary, a genome, a code base), it pays to build an index once.
Tries and autocomplete
A trie (from retrieval; the name is Edward Fredkin's, from 1960) stores a set of strings as a tree. Each edge is labelled with a character, each node represents the prefix spelled out on the path from the root, and nodes where a stored word ends are marked. Words that share a prefix share the path for it. Looking up a word, or finding whether any word starts with a given prefix, takes steps for a query of length , independent of how many words are stored. That is exactly what autocomplete needs: walk down the prefix the user has typed, then list the words in that subtree, best first.
Tries are the tree cousin of the hash table: a hash table answers "is this exact word present?" just as fast, but it cannot answer "which words start with ka?" without looking at every key. Their cost is memory: one node per distinct prefix, each with its own table of children. Production systems compress chains of single-child nodes into one edge labelled with a whole substring (a radix tree or Patricia trie); IP routers use exactly such tries over the bits of addresses, as you will see in Networks. Add "failure links" that play the role of KMP's prefix function and you get the Aho–Corasick automaton, which finds every occurrence of thousands of patterns in one pass over the text; it was invented in 1975 for bibliographic search and still sits inside network intrusion-detection systems and many tools that search for a long list of fixed strings at once.
Suffix arrays
A trie of all the suffixes of a text would answer any substring query: occurs in exactly when is a prefix of some suffix of . That trie can have nodes, though. The suffix array, introduced by Manber and Myers, keeps the idea and drops the memory: it is just the list of starting positions of all suffixes, sorted alphabetically by the suffix that starts there. All the suffixes that begin with are adjacent in that order, so two binary searches find the whole block of matches in character comparisons.
class TrieNode:
def __init__(self):
self.children = {} # character -> TrieNode
self.count = 0 # how often this exact word was entered (0: not a word)
class Trie:
def __init__(self):
self.root = TrieNode()
self.nodes = 1
def add(self, word, times=1):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
self.nodes += 1
node = node.children[ch]
node.count += times
def complete(self, prefix, k=3):
"""The k most frequent words that start with prefix (ties broken alphabetically)."""
node = self.root
for ch in prefix: # walk down: O(len(prefix))
if ch not in node.children:
return []
node = node.children[ch]
found, stack = [], [(node, prefix)]
while stack: # collect every word below that node
node, word = stack.pop()
if node.count:
found.append((-node.count, word))
for ch, child in node.children.items():
stack.append((child, word + ch))
return [word for _, word in sorted(found)[:k]]
searches = {"lagos": 9, "lahore": 7, "lima": 8, "lilongwe": 3, "lisbon": 6,
"luanda": 4, "lusaka": 5, "lyon": 4, "lima peru": 2, "kyiv": 6,
"kyoto": 7, "karachi": 8, "kathmandu": 5, "kampala": 4}
trie = Trie()
for city, times in searches.items():
trie.add(city, times)
for typed in ["l", "li", "ly", "ka", "ky", "x"]:
print(f"{typed!r:6} -> {trie.complete(typed)}")
letters = sum(len(c) for c in searches)
print(f"{len(searches)} words, {letters} letters, {trie.nodes} trie nodes (shared prefixes are stored once)")
# A suffix array: the starting positions of all suffixes, in sorted order.
def suffix_array(s):
return sorted(range(len(s)), key=lambda i: s[i:]) # fine for small s; real ones are O(n)
def occurrences(s, sa, p):
"""All positions of p in s by binary search over the sorted suffixes."""
lo, hi = 0, len(sa)
while lo < hi: # find the first suffix that is >= p
mid = (lo + hi) // 2
if s[sa[mid]:sa[mid] + len(p)] < p:
lo = mid + 1
else:
hi = mid
start = lo
while lo < len(sa) and s[sa[lo]:sa[lo] + len(p)] == p:
lo += 1 # the matches sit next to each other
return sorted(sa[start:lo])
s = "papaya"
sa = suffix_array(s)
for rank, i in enumerate(sa):
print(rank, i, s[i:])
print("'pa' at", occurrences(s, sa, "pa"), " 'a' at", occurrences(s, sa, "a"), " 'ya' at", occurrences(s, sa, "ya"))Notice lima and lima peru: a word can end at a node that also has children, which is why nodes carry a count rather than being "leaves". The suffix array of papaya lists the suffixes a, apaya, aya, papaya, paya, ya; the two suffixes starting with pa are neighbours, at ranks 3 and 4.
The one-line construction above sorts suffixes with comparisons that can each cost , so it is in the worst case; fine for a word, hopeless for a genome. Linear-time constructions exist (SA-IS is the one most libraries use), and adding the LCP array (the length of the longest common prefix of neighbouring suffixes) lets a suffix array answer questions like "what is the longest repeated substring?" in one scan. A close relative, the Burrows–Wheeler transform with its FM-index, lets DNA read aligners such as BWA search a whole human genome held in a few gigabytes of memory.
What is a character?
Every algorithm above compares "characters" for equality. On real text that word hides several different things, and getting them confused produces bugs that only appear for some languages.
- A byte is eight bits. In UTF-8 a character takes one to four bytes (the encoding is explained in Representing data).
- A code point is a number Unicode assigns to an abstract character, written U+00E9 for é. A Python
stris a sequence of code points;lencounts them ands[i]returns one. - A grapheme cluster is what a reader perceives as one character: what the cursor jumps over, what "reverse this string" should keep intact. Unicode Annex #29 defines it, and it can span many code points.
import unicodedata
composed = "café" # é as a single code point, U+00E9
decomposed = "café" # e followed by U+0301 COMBINING ACUTE ACCENT
print(composed, decomposed, composed == decomposed, len(composed), len(decomposed))
def nfc(s):
return unicodedata.normalize("NFC", s)
print("equal after NFC:", nfc(decomposed) == composed)
menu = "Un café, por favor."
print("plain search:", decomposed in menu, " normalised search:", nfc(decomposed) in nfc(menu))
for s in ["नमस्ते", "\U0001F1F3\U0001F1EC", "\U0001F44D\U0001F3FD", "\U0001F469\U0001F4BB"]:
names = [unicodedata.name(c, "?") for c in s]
print(s, len(s), "code points:", ", ".join(names))
print("reversing the flag of Nigeria by code points:", "\U0001F1F3\U0001F1EC"[::-1])
print("straße".upper(), " casefold equal:", "Straße".casefold() == "STRASSE".casefold())
print("dotted capital I lowercases to", len("İ".lower()), "code points:", [hex(ord(c)) for c in "İ".lower()])Four lessons hide in that output.
- The same text can have different code points.
cafécan be stored with a precomposedéor witheplus a combining accent. They look identical and compare unequal, so a search for one misses the other. The fix is normalisation: convert both text and pattern to the same form (NFC, composed, is the usual choice for storage; Annex #15 defines all four forms) before matching. lendoes not count what a reader sees. The Hindi greeting नमस्ते is six code points but only three or four visible units, depending on how the segmentation rules treat its conjunct; a flag is two "regional indicator" code points; a thumbs-up with a skin tone is two; "woman technologist" is three, glued by an invisible ZERO WIDTH JOINER. Reversing a string code point by code point turns the flag of Nigeria (N, G) into the flag of Guinea (G, N). Truncating a message "to 20 characters" by code points can cut an emoji or a conjunct in half.- Case is language-dependent.
ßuppercases to two letters, souppercan change a string's length. Turkish distinguishes dotted and dotless i, and Python's language-neutrallowerturns the capitalİinto two code points. For case-insensitive matching usecasefold, and for user-facing text use a locale-aware library. - Your algorithms are still correct, on the right alphabet. KMP, Rabin–Karp, tries and suffix arrays work on any sequence of symbols. The engineering decision is which symbols: bytes (fast, and fine for exact matching of normalised UTF-8), code points (Python's default), or grapheme clusters (what users mean), with normalisation applied first.
Common misconceptions
Misconception
"The naive algorithm is , so it is always slow." Its worst case is , but on natural-language text most shifts fail at the first character and the average is close to linear. The worst case matters when inputs can be adversarial or highly repetitive (DNA, logs, machine-generated text), and those are exactly the places where a guaranteed linear algorithm earns its keep.
Misconception
"KMP is what real search tools use." KMP's guarantee is beautiful, but it reads every text character. Practical searchers usually prefer Boyer–Moore-style algorithms, which compare the pattern from its right end and can skip ahead by up to characters on a mismatch, so on long patterns over large alphabets they look at only a fraction of the text. CPython's str.find is a tuned hybrid of this kind, switching to the Two-Way algorithm of Crochemore and Perrin (linear worst case, constant extra space) for long patterns; its source file is linked in the references and is worth reading.
Misconception
"Equal hashes mean equal strings." A hash is a fingerprint, not an identity. Rabin–Karp must verify every hash match, or accept that it is a Monte Carlo algorithm that is occasionally wrong. Skipping the check is a classic source of rare, unreproducible bugs.
Misconception
"str.count counts occurrences." It counts non-overlapping occurrences: "abababab".count("abab") is 2, while the pattern occurs at three shifts. Decide which one your problem needs.
Where these ideas came from, and where they live
Morris and Pratt found the linear-time matcher around 1970, and Knuth arrived at it independently from automata theory; the three published together in 1977, the same year Boyer and Moore published their skipping algorithm. Aho and Corasick's multi-pattern automaton dates from 1975, Rabin and Karp's fingerprinting from 1987, and suffix arrays from Manber and Myers around 1990, with linear-time construction following in the 2000s.
Today the ideas are everywhere, usually inside a library:
- Editors and command-line tools (
grep,ripgrep, your IDE's search) combine Boyer–Moore-style skipping, Aho–Corasick for sets of literals, and automata for regular expressions, which reappear as the first stage of every compiler in Compilers and interpreters. - Bioinformatics lives on suffix arrays, FM-indexes and -mer hashing, which is Rabin–Karp's rolling hash applied to every length- window of a genome.
- Search engines use inverted indexes over words rather than substring indexes, and tries for query suggestions.
- Spell checking and fuzzy search need to know how far apart two strings are. That is edit distance, the dynamic programme from Dynamic programming, often combined with a trie so that whole subtrees of the dictionary are abandoned once the distance exceeds a limit.
- Every system that handles user text needs the Unicode discipline of the previous section: normalise on input, compare with
casefold, and count grapheme clusters when the user's notion of "character" matters.
Exercises
1. String algorithms
Warm-upHumanCompute the prefix function of the pattern abcababcab by hand, the way the lesson did for ACAACAC. What is , the length of the longest proper border of the whole pattern?
2. String algorithms
Warm-upHumanThe text has length and the pattern has length . Which text and pattern make the naive algorithm do close to character comparisons?
3. String algorithms
CoreComputationalWrite prefix_function(p), returning the list pi where pi[i] is the length of the longest proper border of p[:i+1]. Your function must run in time for a pattern of length (no trying every possible border length), so use the fall-back idea from the lesson rather than comparing slices.
4. String algorithms
Warm-upHumanHow many times does the pattern abab occur in the text abababab, counting overlapping occurrences (that is, how many shifts satisfy abab)?
5. String algorithms
CoreHumanYou run Rabin–Karp on a text of characters with a pattern of length that does not occur in the text, using a modulus (a prime) and a base chosen at random. Treat each window's hash as if it were a uniformly random value modulo . About how many false alarms (windows whose hash equals the pattern's hash) do you expect? Give the nearest whole number.
6. String algorithms
CoreComputationalComplete the Trie class. add(word) stores a word; starts_with(prefix) returns a sorted list of every stored word that begins with prefix (the empty prefix returns every word). Store words in nested dictionaries: each node is a dict from characters to child nodes, and the special key "$" marks that a word ends at that node. (The tests only use lower-case letters and spaces, never $.)
7. String algorithms
CoreHumanA genomics lab has one fixed reference genome of about letters. Every day it receives millions of short reads (about 150 letters each) and must find where each read occurs in the reference. Which approach fits best?
8. String algorithms
CoreHumanWhich of these statements about Python 3 strings are true? Select all that apply.
Further reading and resources
- Fast pattern matching in strings · Donald E. Knuth, James H. Morris Jr. and Vaughan R. Pratt · 1977The KMP paper, SIAM Journal on Computing.
- Efficient randomized pattern-matching algorithms · Richard M. Karp and Michael O. Rabin · 1987Fingerprinting with random hashes, including the rolling hash.
- A fast string searching algorithm · Robert S. Boyer and J Strother Moore · 1977The algorithm that skips ahead, behind many practical search tools.
- Efficient string matching: an aid to bibliographic search · Alfred V. Aho and Margaret J. Corasick · 1975A trie with failure links that finds many patterns in one pass.
- Suffix arrays: a new method for on-line string searches · Udi Manber and Gene Myers · 1993
- Two efficient algorithms for linear time suffix array construction · Ge Nong, Sen Zhang and Wai Hong Chan · 2011SA-IS, the linear-time construction used by many libraries.
- Unicode Standard Annex #15: Unicode Normalization Forms
- Unicode Standard Annex #29: Unicode Text SegmentationWhere "user-perceived character" (grapheme cluster) is defined.
- CPython's string search (fastsearch.h)What
inandstr.findactually do, with comments explaining the design.