This site has twelve 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. The other two answer genuinely different questions and sit outside the comparison below, the same way the Range Query guide sets seven of its own thirteen 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 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 while keeping most of the practical speed on
non-adversarial text — 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: both algorithms'
own Pitfalls sections measure the identical periodic-input pathology, 9,910 comparisons
against naive's 10,000 on the same adversarial input, because neither implements
Galil's rule to detect and exploit its own previous match.
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.