Text Search §

Why the naive scan is quadratic. The naive algorithm aligns the pattern at each of the $n-m+1$ positions and compares up to $m$ characters: $O(nm)$. The key observation behind every linear algorithm is that a mismatch at position $i$ tells you something about the next alignment, so you should not re-examine characters you already know match.

KMP — the prefix function. The prefix function $\pi[j]$ is the length of the longest proper prefix of $P[0..j]$ that is also a suffix of it. When a mismatch happens at pattern index $j$, KMP slides the pattern so that the already-matched prefix of length $\pi[j-1]$ lines up, and resumes comparing at index $\pi[j-1]$. This is exactly the “jump” that avoids re-scanning.

Worked example. Let $P = \texttt{ababac}$ ($m = 6$) and $T = \texttt{ababababac}$ ($n = 10$).

Prefix function of $P$:

Trace ($j$ = how many pattern characters currently match):

The single match is at position 4: $T[4..9] = \texttt{ababac}$. Notice the two mismatches at $i = 5$ and $i = 7$: instead of restarting at $j = 0$, KMP jumps to $j = 3$ because the prefix “aba” of the pattern is also the suffix of what matched so far.

Boyer–Moore. Compare from the right end of the window. The bad-character rule shifts the pattern so that the mismatching text character aligns with its rightmost earlier occurrence in the pattern (or past the pattern if it is absent). The good-suffix rule shifts so that a matched suffix re-aligns with an equal prefix. Both shifts are at least 1, and on a large alphabet the average shift is large, giving $O(n/m)$ comparisons.

Rabin–Karp. Maintain a hash of the current window $T[i..i+m-1]$ and compare it to the hash of $P$. When the window slides by one, update the hash in $O(1)$ (drop the leftmost character’s contribution, shift, add the new rightmost character). A hash match triggers a full $O(m)$ verification, so the expected time is $O(n+m)$ but the worst case (many collisions) is $O(nm)$.

Authoritative source: CLRS Ch. 32 (String Matching), pp. 831–866. Knuth, Morris & Pratt, “Fast pattern matching in algorithms” (1977).

Step 1 — The structure. A trie is a rooted tree. The root represents the empty string. Each edge from a node is labeled by one character; the path from the root to a node spells the string stored at that node. A node is marked terminal when the spelled string is a complete member of the set. Because shared prefixes share nodes, the trie is compact for sets with many common prefixes.

Step 2 — Worked example. Insert the words cat, car, card, dog. The prefixes “ca” and “car” are shared, so they occupy a single path.

Step 3 — Operations.

• Insert “car”: walk c → a → r, mark the “r” node terminal. $O(L)$.
• Lookup “card”: walk c → a → r → d; the “d” node is terminal → found. $O(L)$.
• Prefix query “ca”: walk to the “a” node, then DFS its subtree to collect all terminal nodes (cat, car, card). $O(|p| + k)$.

Step 4 — Space. With $N$ total characters across all stored strings, the trie has at most $N+1$ nodes (one per distinct prefix, plus the root). If each node stores a full array of $\sigma$ child pointers, the space is $O(N \cdot \sigma)$. For a large alphabet (e.g. Unicode), this is wasteful, so real implementations store a sparse map (or a sorted child list) per node, dropping the $\sigma$ factor to the actual branching.

Step 5 — Variants. A radix tree (or Patricia trie) compresses unary chains into single edges labeled by a string, shrinking the tree for sparse data; it is the standard structure for longest-prefix matching such as IP routing. A double-array trie maps the tree into two arrays for cache-friendly, disk-resident lookup.

Authoritative source: CLRS Ch. 32.3 (Tries). Crochemore & Rytter, “Jewels of the Stringology” (2002), Ch. 2.

Step 1 — The suffix array. The suffix array $SA$ is a permutation of $0..n-1$ such that the suffixes $T[SA[i]..]$ are in lexicographic order. A pattern $P$ occurs in $T$ iff it is a prefix of some suffix, i.e. iff the suffixes having prefix $P$ form a contiguous interval in $SA$. Finding that interval is a binary search: $O(m \log n)$.

Step 2 — Worked example. Let $T = \texttt{banana}$ ($n = 6$).

So $SA = [5, 3, 1, 0, 4, 2]$ and the LCP array (longest common prefix of each suffix with its predecessor) is $LCP = [0, 1, 3, 0, 0, 2]$.

Step 3 — Counting matches with LCP. Once the binary search locates the interval of suffixes prefixed by $P$, the number of matches is the number of entries in that interval whose LCP value is at least $m$ (the pattern length). For $P = \texttt{ana}$ ($m = 3$), the interval is ranks 1–2 (suffixes “ana”, “anana”); both have LCP ≥ 3 within the interval, so there are 2 matches, at original indices 3 and 1.

Step 4 — The suffix tree. The suffix tree is the compact trie of all suffixes: internal nodes have at least two children and edges are labeled by strings (unary chains are compressed). A query walks the tree following $P$ in $O(m)$, then counts the leaves in the reached subtree in $O(k)$. Total $O(m + k)$. It is the most query-efficient structure but harder to build and maintain.

Step 5 — The FM-index. The FM-index does not store the suffix array explicitly. It stores:

1. The Burrows–Wheeler transform (BWT) of $T$ — a permutation of the characters that groups similar contexts together (highly compressible).
2. A C-array: for each character $c$, the number of characters in the BWT that are lexicographically smaller than $c$.
3. Rank structures (succinct bitvectors or a wavelet tree) that answer $\text{rank}_c(i)$ = the number of occurrences of $c$ in $BWT[0..i]$.
4. A sampled suffix array (one entry every $B$ rows) so that match positions can be reported by walking back from a sample.

A query runs backward search: starting from the whole BWT, it repeatedly narrows the row interval $[lo, hi)$ by one character of $P$ (read right-to-left) using the C-array and rank. Each step is $O(\log \sigma)$, so the whole query is $O(m \log \sigma)$, in $O(n)$ space (often under 2 bits per character). This is the index behind bwa/bowtie genome aligners.

Authoritative sources: CLRS Ch. 32.4 (Suffix Trees). Manber & Myers, “Suffix arrays: a new method for on-line string searches” (1993). Ferragina & Manzini, “Indexing string databases” (2000).

Step 1 — The inverted index. Instead of storing “document → its terms” (a forward index), the inverted index stores “term → documents containing it”. Each entry (a posting list) is a sorted list of document IDs, optionally with term frequencies and positions.

A query for multiple terms is answered by intersecting the posting lists (AND) or merging them (OR). Because the lists are sorted, an intersection is a linear merge in the total list lengths.

Step 2 — TF-IDF. The raw term frequency $f(t, D)$ rewards documents that mention $t$ often, but a term like “the” appears everywhere and is uninformative. TF-IDF down-weights common terms:

where $N$ is the number of documents and $n(t)$ is the number of documents containing $t$. A term that appears in few documents (large $N/n(t)$) gets a high weight.

Step 3 — BM25. TF-IDF has two problems: the term frequency grows without bound, and long documents are unfairly favored. BM25 fixes both. It saturates the frequency with a parameter $k_1$ and normalizes by document length with a parameter $b$:

Typical values are $k_1 \in [1.2, 2.0]$ and $b \in [0.75, 1.0]$. The fraction approaches $k_1 + 1$ as $f(t, D) \to \infty$ (saturation), and the length term penalizes documents longer than average.

Authoritative source: Robertson, S. E., & Spärck Jones, K. (1994). “Relevance weighting of search terms.” Journal of the American Society for Information Science, 45(7), 520–536. DOI: 10.5555/106765.106783.

Step 4 — n-grams and fuzzy matching. To tolerate typos, index the words by their n-grams (substrings of length $n$) and require a candidate to share enough n-grams with the query. The arithmetic: a word of length $L$ has $L - 1$ bigrams, and a single edit (insert, delete, or substitute) changes at most 2 bigrams. So a word within edit distance $d$ of the query shares at least $(L - 1) - 2d$ bigrams with it.

Example: the query elephant (length 8) has 7 bigrams: el, le, ep, ph, ha, an, nt. A candidate within edit distance 2 must share at least $7 - 2\cdot 2 = 3$ bigrams. The typo elephat (one deletion) shares el, le, ep, ph, ha = 5 bigrams ≥ 3, so it passes the filter. An unrelated word like computer shares 0 bigrams and is rejected before any expensive edit-distance computation. (Note: a string of length 10 has 9 bigrams, not $\binom{10}{2}$ — the latter counts 2-element subsets, not substrings.)

Authoritative source: Manku, Baeza-Yates & Jain, “Efficient computation of edit distance” (2006).

Step 1 — Scaling the index. A single machine cannot hold the inverted index of a web-scale corpus. The standard design shards the corpus: documents are partitioned (by document-ID hash) across nodes, and each node builds and serves the inverted index for its shard. A query is fanned out to all shards, which return their top-$k$ locally, and a coordinator merges the per-shard ranked lists into a global top-$k$. Posting lists are compressed with delta encoding + variable-byte or bit-packing, and term dictionaries are stored in a B-tree or a hash table for fast lookup.

Step 2 — Keyword vs. semantic search. Keyword retrieval (the inverted index above) matches on exact terms: a query for “car” will not return documents that only say “automobile”. Vector / embedding-based (semantic) search instead maps each document and the query to a high-dimensional dense vector (an embedding) and ranks by a similarity measure such as cosine similarity or inner product. This captures meaning and paraphrase but cannot do exact-term or positional matching, and the nearest-neighbor search over millions of vectors requires its own index (e.g. an approximate nearest-neighbor structure). Modern engines run hybrid search: the inverted index for precision and the vector index for recall, then fuse the two ranked lists.

Authoritative source: Zobel & Moffat, “Inverted files for text search engines” (2006).

Step 1 — From regex to automaton. The theoretical foundation is that every regular expression denotes a regular language accepted by a finite automaton (see Computability and Complexity Classes for the automata and decidability background). Thompson’s construction builds an NFA for a regex in linear time, using only $\varepsilon$-transitions (transitions that consume no input):

• A literal $c$: a two-state NFA with a $c$-labeled edge.
• Concatenation $AB$: wire the accept state of $A$ to the start of $B$ with an $\varepsilon$-edge.
• Alternation $A|B$: a new start $\varepsilon$-branches to $A$ and $B$; both accept states $\varepsilon$-merge into a new accept.
• Repetition $A*$: a new start $\varepsilon$-branches into $A$ and directly to a new accept; $A$’s accept $\varepsilon$-loops back to its start and also $\varepsilon$-exits.

Step 2 — The NFA for “ab*”. The regex $\texttt{ab*}$ (an “a” followed by zero or more “b”s) compiles to:

Step 3 — Running the NFA: Thompson simulation. An NFA can be in many states at once. Thompson’s algorithm keeps the set of active states and, for each input character, computes the next active set by following $\varepsilon$-closures and character edges. This is $O(n)$ in the input length (each state is processed a bounded number of times). The Pike VM (used in grep) is a compiled, instruction-based version of the same idea.

Step 4 — Backtracking vs. automata. A backtracking engine walks the regex and the text together, and on a failed branch it undoes the last choice and tries the next. It is easy to implement and supports powerful features (lookaheads, backreferences), but a regex like $\texttt{(a+)+b}$ against the input $\texttt{aaaa...a}$ (no “b”) explores an exponential number of ways to split the “a”s — catastrophic backtracking. Automaton engines have no such blowup because they track a set of states, not a single path. In practice, grep/ripgrep use automata for speed and safety, while language regex libraries often use backtracking for expressiveness.

Authoritative sources: Thompson, “Regular expression search algorithm” (1968). Pike, “The Pike programming language” (1988).

You are building a spell-checker over a dictionary of 100,000 English words and must suggest corrections for a mistyped word of length 8 within edit distance 2. You have two candidate designs:

1. For each dictionary word, compute the full edit distance to the query and keep those ≤ 2.
2. Index every dictionary word by its bigrams; for the query, keep only dictionary words that share at least 3 bigrams, then compute the full edit distance only on those survivors.

Which design is faster in practice, and why? (Hint: how many bigrams does the query have, and how many bigrams can 2 edits destroy?)