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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
| Entry | Patterns | Searches | Time | Worst 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 |
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.