String Matching

Abstract

Finding one string inside another looks like the most elementary thing a computer does, and the naive method (slide the pattern along, compare character by character) is what almost everyone writes and what almost every program used for decades. The theory underneath is stranger. The fastest classical algorithm gets faster the longer the pattern is, and the cleanest of them fell out of an attempt to understand an obscure result about pushdown automata. This article follows string search from the brute-force loop to Knuth-Morris-Pratt and Boyer-Moore in 1977, to the suffix tree that lets you index a text once and answer any query about it, and to why a genome is the killer application.

The Obvious Method and Its Cost

To find the pattern P of length m in the text T of length n, line them up at the left, compare characters until one mismatches or the pattern runs out, then shift the pattern one place right and start over. It works and it is what a first-year student writes. Its cost is the problem: on adversarial input like searching aaaaab inside a long run of as, every alignment compares almost the whole pattern before failing at the last character, giving roughly n·m comparisons. For the strings people actually search this is rarely triggered, which is why the naive loop survived so long in practice. The theorists’ objection was that it throws away information. When abcabd fails to match at the d, the algorithm already knows the last five text characters were abcab, yet it shifts by one and re-examines characters it has already seen. The good algorithms never look backward.

Knuth, Morris, and Pratt

The first algorithm to search in guaranteed linear time came out of automata theory rather than a desire for a faster grep. In 1971 Stephen Cook proved a theorem about two-way deterministic pushdown automata: any language such a machine recognizes can be recognized by a random-access machine in time linear in the input length. The result was abstract and looked useless. Donald Knuth read it, noticed that “does P occur in T” is exactly such a language, and mechanically cranked Cook’s construction to see what program it produced. Out came a string matcher that never backs up over the text and runs in O(n + m) time. Knuth had derived it from theory a few weeks after James Morris had already invented essentially the same thing by hand: Morris, writing a text editor, had built a matcher that avoided backing up because backing up in a buffered editor was painful to implement. Vaughan Pratt connected the two. The three held the result from 1970 until they published “Fast Pattern Matching in Strings” jointly in the SIAM Journal on Computing in 1977.

The idea is a precomputed failure function. Before touching the text, the algorithm analyzes the pattern to answer: if I have matched the first k characters and the next one fails, what is the longest prefix of the pattern that is also a suffix of what I just matched, so I can resume from there without rereading the text? That table lets the search pointer move only forward. The Russian mathematician Yuri Matiyasevich had published a similar linear-time matcher in 1969, using a two-dimensional Turing machine, a fact Western computer science noticed only much later.

Boyer and Moore, or Reading Backwards

The same year, Robert Boyer and J Strother Moore published “A Fast String Searching Algorithm” in Communications of the ACM with a counterintuitive twist: compare the pattern to the text from right to left. When the rightmost character of the pattern lines up against a text character that appears nowhere in the pattern, you can jump the whole pattern past that position in one move, skipping m characters without ever looking at them. The consequence is that Boyer-Moore runs faster as the pattern gets longer: on typical text it examines a fraction of the characters, sublinear on average, roughly O(n/m) in the good cases. This is the algorithm inside grep, inside editors’ find commands, and inside the memmem routines of standard libraries. Two shift rules drive it, the “bad character” rule (jump based on the mismatched text character) and the “good suffix” rule (jump based on the pattern’s own repeated structure), and combining them gives worst-case linear behavior as well.

Indexing the Text Once

KMP and Boyer-Moore preprocess the pattern. That is the right trade when the text changes and the pattern is fixed for one search. The opposite trade, preprocess the text so that any pattern can then be found instantly, needs a different structure. The suffix tree is that structure: a compressed tree holding every suffix of the text, built so that searching for any pattern of length m takes O(m) time regardless of how big the text is. Peter Weiner introduced it in 1973; Knuth reportedly called it the “algorithm of the year”. Edward McCreight simplified the construction in 1976, and Esko Ukkonen gave a cleaner online version in 1995 that builds the tree left to right as characters arrive. The catch is memory: a suffix tree can consume ten to twenty times the size of the text it indexes, which later drove the invention of the leaner suffix array.

Why Biology Cares

String matching left the realm of text editors when the strings became genomes. DNA is a string over a four-letter alphabet, hundreds of millions to billions of characters long, and the central operations of genomics (find this gene, align these two sequences, locate every near-repeat) are string-matching problems at a scale that makes the choice of algorithm decide whether an analysis finishes in an hour or a week. The BLAST tool, from 1990, made sequence search fast enough to be routine, and suffix trees and their descendants underpin the aligners that map billions of short sequencing reads back onto a reference genome. The rise of cheap sequencing turned an elegant corner of algorithm theory into daily infrastructure for biology, a story continued in Bioinformatics and the Human Genome. The regular-expression engines that grew out of the same search tradition are part of Ken Thompson’s Unix legacy, where grep began.