Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing an Exact-Match String Matcher

This site has sixteen exact match entries now, but only ten answer the same underlying question — given a pattern, where does it occur in a text: KMP, Aho-Corasick, Rabin-Karp, Boyer-Moore, Boyer-Moore-Horspool, Z-Algorithm, Suffix Array, Suffix Tree, Suffix Automaton, and FM-Index — each built, verified, and explained on its own page. Two more answer genuinely different questions and sit outside the comparison below, the same way the Range Query guide sets fourteen of its own twenty Array-Backed Trees entries aside before comparing the rest: Manacher's Algorithm finds the longest palindromic substring of one string with no pattern at all, and Burrows-Wheeler Transform doesn't search at all — it's a reversible rearrangement used to make a text more compressible or to build a different kind of index entirely (FM-Index is what you get when you build a search structure directly on top of that rearrangement instead). The thirteenth, fourteenth, fifteenth, and sixteenth, Galil's Rule, Suffix Array Construction (Prefix Doubling), Suffix Array Induced Sorting (SA-IS), and Suffix Tree Construction (Ukkonen's Algorithm), aren't searches of their own at all — one is a refinement layered onto Boyer-Moore, two build the array Suffix Array already searches just faster and faster still, and the fourth builds the tree Suffix Tree already searches, the same structure in O(n) instead of O(n²) — all four covered in their own asides below rather than the ten-way comparison. The site's first guide already sorted the approximate side of string matching by which problem you have; the ten pattern-matching entries here grew past that size — the site's largest single comparison — without the same treatment. This guide sorts those ten not by algorithm name but by two questions that come before any complexity comparison: how many patterns, and how many searches.

Three questions, not one algorithm

In order, cheapest to check first: Are you matching more than one pattern in a single pass over the text? If so, nine of the ten entries are the wrong shape for the job — they all assume exactly one pattern, and running one of them once per pattern rescans the text from scratch every time. Will the same text be searched again and again, for patterns that aren't known yet? If so, six of the ten pay their whole cost fresh on every search — four of them index the text itself, once, so later searches are cheap no matter how many patterns eventually get asked (the choice between those four is its own question — see below). Otherwise — one pattern, one text, one search — do you need a worst-case guarantee, or is fast on ordinary text good enough? That's where the remaining choice actually lives, between algorithms that are all correct and all cheap in the common case, but differ in what happens when the input is adversarial.

More than one pattern, one pass

Aho-Corasick is the only entry built for this. Its own page states the alternative plainly: run KMP once per pattern and the text gets rescanned from the beginning every time, O(k·(n+m)) total for k patterns. Aho-Corasick instead builds every pattern into one trie, generalizing KMP's failure-link idea from "the pattern compared against itself" to "every trie node compared against every other node," so the text is scanned exactly once regardless of how many patterns are loaded — O(m) to build the trie and its failure links (m the combined length of all patterns), then O(n+z) to scan, where z is the number of matches actually reported. The cost of that generality: building the automaton is real up-front work, and it's specifically wasted if there's only ever going to be one pattern.

Suffix Array, Suffix Tree, Suffix Automaton, and FM-Index all invert the usual relationship. Every other entry on this page compares the pattern against the text at search time, which means the full search cost is paid again for every new pattern. These four instead index the text once, up front, and answer any later pattern — one nobody knew about when the text was indexed — cheaply. All four are a poor fit for the opposite case: a single one-shot search doesn't get to amortize that build cost against anything. Between them, the difference is mechanism and what the index can answer, not just outcome: Suffix Array sorts the suffixes into a flat array — O(n log n) comparator-based sort — and answers each query with a binary search that proves a match exists (O(m log n)) plus a walk outward through the sorted table's matching block to read off all k occurrences (O(m·k)). Suffix Tree instead builds every suffix into one shared, edge-compressed trie, so a query walks straight down from the root matching pattern characters against edge labels — O(m), no log factor at all — at the cost of a heavier structure (real nodes and child pointers, not n plain integers) and a naive build that's unconditionally O(n²) rather than only slow on adversarial or repetitive text the way Suffix Array's naive sort is. Suffix Automaton gives up occurrence positions entirely — as built here, it only answers "is this a substring" and "how many distinct substrings exist," not "where" — in exchange for the only guaranteed O(n) build of the three (online, amortized, no adversarial input makes it worse) and the smallest possible state count for that guarantee, at most 2n−1. FM-Index takes a fourth path entirely: instead of extending either the sorted array or the trie, it reuses the reversible Burrows-Wheeler Transform plus two small derived tables to match the pattern backward, one character at a time, in O(m) steps that never depend on n — no suffix array or original text needs to be kept around at all, only the transform itself, which is the same length and alphabet as the source text rather than an array of n integers or a tree of real node objects. The cost of that compactness is locating each match afterward: proving how many matches exist is free once the range is found, but reading off where each one starts needs a further walk (bounded by sampling the suffix array at an interval, in real implementations) that none of the other three need at all, since their indexes already store positions directly. Reach for Suffix Array when the flat integer array's small footprint matters; reach for Suffix Tree when query speed and occurrence positions both matter more than build time or memory; reach for Suffix Automaton when the question is existence or counting rather than location, and a guaranteed linear build matters more than either; reach for FM-Index when the index itself has to stay small relative to the text — a genome, a large corpus — and paying a bit more to locate each match is an acceptable trade for not storing a full suffix array's worth of integers at all.

One pattern, one text: a guarantee that never breaks

KMP and Z-Algorithm both give an unconditional O(n+m), on every input, with no adversarial case that degrades it — genuinely different mechanisms arriving at the same bound. KMP precomputes a failure-function table sized to the pattern alone (O(m) space) and reuses it as a fallback while scanning the text once, left to right. Z-Algorithm instead glues pattern and text into one string and builds a single Z-array over the whole concatenation, reading every match straight off the finished array with no separate search phase — at the cost of O(n+m) space for that concatenated array, more than KMP's pattern-only table. Reach for KMP when the smaller footprint matters or the pattern is fixed and searched against many separate texts (the table is reusable); reach for Z-Algorithm when the single-array construction is more convenient, or when the same Z-array machinery is useful for something else the codebase already needs.

One pattern, one text: fast on ordinary text

Boyer-Moore and Boyer-Moore-Horspool both trade the unconditional guarantee away for something KMP and Z-Algorithm structurally can't offer: sublinear best/average case, O(n/m), by comparing right to left and skipping several text positions per mismatch instead of examining every character. Full Boyer-Moore keeps two shift rules — bad-character and good-suffix, O(m) preprocessing each — and always takes whichever proposes the bigger jump. Horspool drops the good-suffix rule entirely and keys its one remaining table to a single fixed position (the comparison window's last character) rather than wherever the mismatch actually happened, halving the preprocessing machinery — and, measured directly on non-adversarial text, actually running faster in wall-clock than full Boyer-Moore, not just "most of" its speed (see measuring ordinary text: comparison counts are statistically tied and Horspool wins wall-clock on every size/pattern combination tested), which is why an unqualified "Boyer-Moore" in library code most often means Horspool specifically. Neither has a real worst-case advantage over naive search on its own: both algorithms' own Pitfalls sections measure the identical periodic-input pathology, 9,910 comparisons against naive's 10,000 on the same adversarial input — full Boyer-Moore's own good-suffix table can be extended to fix this (see the aside just below); Horspool has no good-suffix table to extend, so the pathology is unconditional for it.

A refinement, not an eleventh path: Galil's Rule

Galil's Rule only ever applies once full Boyer-Moore has been chosen — it changes nothing about which of the ten paths above to take, so it isn't an eleventh one. It closes the exact gap the previous section just named: after a full match, the next alignment's overlap with the text just read is provably safe to skip rather than re-compare, because the shift used is always a genuine period of the pattern. Checked directly against the identical 1,000-character/10-character periodic input both Boyer-Moore and Boyer-Moore-Horspool's own Pitfalls sections use: 1,000 comparisons instead of 9,910, a real O(n+m), not the marginal gain either shift rule alone provides. It does not extend to Horspool (no good-suffix table means nothing to detect the overlap with), and its own Pitfalls section shows the same skip is unsound if generalized past the full-match case it's scoped to — worth reading before assuming the idea trivially generalizes to every shift.

A faster build, not an eleventh path: Suffix Array Construction

Suffix Array Construction (Prefix Doubling) only ever applies once Suffix Array has been chosen — it produces the identical sorted array that page's own binary search relies on, just faster to build, so it isn't an eleventh path any more than Galil's Rule above is. It closes the gap Suffix Array's own Pitfalls section names: comparing suffixes by slicing and comparing full strings costs up to O(n) character work per comparison, making the naive sort O(n² log n) on repetitive text; this page instead sorts by rank tables built up over O(log n) passes, each comparison O(1) regardless of how long a prefix two suffixes share. Measured directly against the same n = 800 repeated-character input Suffix Array's own page uses: 8,287 comparator calls against that page's 320,399 character comparisons, a real gap that's specific to repetitive text — on random text the two run within a small constant factor of each other either way, since a naive comparison on random text already stops within the first character or two. Two checked pitfalls: skipping rank deduplication after a tied round freezes an arbitrary order permanently instead of letting a later round resolve it, wrong on 79.7% of 30,000 trials; treating a suffix that runs off the end as tied with real rank-0 content instead of as unconditionally smaller is wrong on 38.4% of the same trial count.

Faster still, not a twelfth path: SA-IS

Suffix Array Induced Sorting (SA-IS) only ever applies once Suffix Array has been chosen, same as the aside above — it produces the identical sorted array, just faster to build still, so it isn't a twelfth path any more than Prefix Doubling is an eleventh. It closes the gap Prefix Doubling's own closing paragraph names: that page gets construction down to O(n log² n) by comparing rank pairs instead of raw text, but a genuine O(n) bound needs a different mechanism — classify every suffix as one of two types, induce most suffixes' positions from a small subset's order instead of comparing anything, and recurse on a provably smaller problem only when that subset's order isn't fully known yet. Measured directly, counting every array read/write across all recursion levels: on the identical n = 800 repeated-character input Suffix Array's own page uses, 8,008 operations, growing at an exact 2.00× per doubling of n against Prefix Doubling's own measured ~2.16× — a real gap, though one that needs considerably larger n than either page's demo allows to look dramatic rather than marginal. Two checked pitfalls: naming LMS substrings by a fixed comparison window instead of requiring both to reach their own LMS boundary together is wrong on 2.2% of 30,000 trials; classifying a tied character as the wrong type instead of inheriting the next suffix's is wrong on 40.6% of the same trial count, including builds that leave a slot in the array unfilled entirely rather than merely misordered.

A linear-time build, not a thirteenth path: Suffix Tree Construction

Suffix Tree Construction (Ukkonen's Algorithm) only ever applies once Suffix Tree has been chosen — it produces the identical compressed tree that page's own query walk relies on, just built in O(n) instead of O(n²), so it isn't a thirteenth path any more than the two Suffix Array builders above are an eleventh and twelfth. It closes the gap Suffix Tree's own Complexity section names directly: inserting n suffixes into a raw trie and compressing it afterward costs n(n+1)/2 unconditionally, regardless of what the text shares; this page instead processes one character per phase, using a shared mutable end pointer so every existing leaf grows for free and an active point carried across extensions (via suffix links) so most phases finish in O(1). Measured directly against the identical n = 800 repeated-character input Suffix Tree's own page uses: 801 explicit extensions against that page's 320,400 insertion steps — and unlike the two Suffix Array builders above, this exact input is close to this algorithm's cheapest case, not a stress test: the same repetition that makes naive character comparison expensive is exactly what lets this page's early-stop rule skip almost every phase for free. Two checked pitfalls: freezing a new leaf's end at creation instead of pointing it at the shared, growing end value silently truncates every leaf and is wrong on 99.8% of 20,000 trials; letting the "already present" early-stop fall through and consume a pending suffix instead of leaving it for a later phase silently drops suffixes and is wrong on 80.2% of the same trial count.

Skip comparison entirely: fingerprint first

Rabin-Karp is the one entry here that isn't a variation on character-by-character comparison at all. It hashes the pattern once and rolls a numeric fingerprint across the text one window at a time, an O(1) update per window, and only falls back to comparing actual characters when two fingerprints collide. With a well-chosen large prime modulus that's rare, giving expected O(n+m) overall — but a bad modulus, or an adversarial input crafted against a known one, forces verification on every window and degrades to O(nm), identical to naive search. It's rarely the fastest choice on this page for a single pattern against a single text, but the fingerprint-first mechanism generalizes in ways character comparison doesn't — checking many equal-length patterns against the same windows, for instance — which is why it's worth knowing on its own terms rather than only as a fallback.

Side by side

EntryPatternsSearchesTimeWorst case
Aho-Corasick many, one pass one text scan O(m) build, O(n+z) scan O(m) build, O(n+z) scan — unconditional
Suffix Array one at a time, unknown in advance reused across any number of queries O(n log n) build, O(m log n + m·k) per query build can hit O(n² log n) on repetitive text
Suffix Tree one at a time, unknown in advance reused across any number of queries O(n²) build (naive, unconditional), O(m + k) per query build is always O(n²), regardless of input
Suffix Automaton one at a time, unknown in advance reused across any number of queries O(n) build (online, amortized), O(m) per query, no occurrence positions O(n) build — unconditional, the only one of the three with no worse case
FM-Index one at a time, unknown in advance reused across any number of queries O(n log n) build (naive), O(m) per query, O(occ · locate steps) to find positions build shares Suffix Array's repetitive-text trap; query itself is unconditional O(m)
KMP one one O(n+m) O(n+m) — unconditional
Z-Algorithm one one O(n+m), O(n+m) space O(n+m) — unconditional
Boyer-Moore one one O(n/m) best/avg O(nm) — periodic input defeats both shift rules
Boyer-Moore-Horspool one one O(n/m) best/avg O(nm) — identical to naive on periodic input
Rabin-Karp one (extends to equal-length sets) one O(n+m) expected O(nm) — modulus collisions force verification

What none of these ten do

Every algorithm above answers the same question — does the pattern occur exactly — just by different mechanisms and under different reuse assumptions. None of them tolerate a single typo, dropped character, or transposition; a text that's one character off from the pattern is, to all ten, simply not a match. That's a different problem with its own guide: see Choosing an Approximate String Matcher for the site's six entries that search or compare while forgiving some number of edits, rather than demanding an exact match.

This is the site's fourth guide, following the same pattern as the first three: a cross-cutting page comparing existing entries instead of adding a new algorithm, for a family that had grown large enough (now ten entries, the site's largest single comparison) that "which one do I use" is a real question a reader would have. See the journal for this session's notes.