A change of strategy: preprocess the text
Every method so far in this rung shared one habit: spend a little time studying the pattern, then sweep the text once. KMP precomputes a prefix-failure table, the Z-algorithm builds a Z-array, Rabin-Karp uses a rolling hash — but in all of them the text is read fresh on every search. That is exactly right when the text changes constantly and the pattern is fixed. This guide explores the mirror-image situation, and it is just as common: the text is fixed and queried again and again. A genome you will probe with thousands of patterns; a book you will search a hundred times. When the text is the stable part, it pays to preprocess it instead.
Two distinct goals live under this umbrella, and it helps to keep them apart. The first: you have many patterns and want to find all of them in one pass over the text — that is the multi-pattern problem, solved by Aho-Corasick. The second: you have one text and want to answer any future substring question about it almost instantly — does pattern P occur, how many times, where? — that is the text-indexing problem, solved by the suffix tree and its flatter cousin the suffix array. Different goals, but the same shift in mindset: pay an upfront cost on the text to make every later query cheap.
Aho-Corasick: KMP grown a tree
Suppose you must scan a text for a whole dictionary of words at once — say {he, she, his, hers}. Running KMP separately for each word means re-reading the text once per word, costing O(k*n) for k patterns over a text of length n. Aho-Corasick does it all in essentially one pass. The first ingredient is a trie: glue all the patterns into a single tree where shared prefixes share a path. "he", "hers", and "his" all start at the same h-node; "hers" simply extends the "he" path. Each node marks whether a pattern ends there. Now imagine feeding the text in one character at a time, walking down the trie — as long as characters keep matching, you descend, and whenever you land on a node marked as a pattern end, you have found an occurrence.
But what happens when the next character fails to match in the trie? Here is the beautiful part, and it is pure KMP thinking. Instead of restarting at the root and wasting everything you matched, you follow a failure link to the deepest other trie node whose label is a proper suffix of where you are. This is exactly the prefix-failure idea from the failure function guide, lifted from a single string onto a tree: when you cannot extend a match, fall back to the longest already-matched suffix that is also a prefix of some pattern, and continue from there without rereading the text. Those failure links are built once with a breadth-first sweep over the trie, each node's link computed from its parent's link — the very same bootstrapping recurrence that fills KMP's table, now branching across a tree.
The payoff is clean. Building the automaton takes time proportional to the total length of all patterns, call it m; scanning the text is O(n) plus the cost of reporting matches; so the whole job is O(m + n + z) where z is the number of matches found. That last z term is unavoidable and honest — if a million matches exist you must spend time listing a million matches, no algorithm can dodge that output cost. Compare this with the naive O(k*n) of running each pattern separately: Aho-Corasick replaces the factor of k with a single sweep, which is exactly why it powers things like intrusion-detection rule sets and virus scanners that hunt thousands of signatures simultaneously.
Suffix trees: indexing every substring at once
Now the second goal: one fixed text T, queried by many future patterns. The key observation is small but powerful — every substring of T is a prefix of some suffix of T. The substring "ana" in "banana" is the start of the suffix "anana" (and of "ana"). So if we build a structure that lets us walk down any suffix from the start, we can test any pattern by walking it character by character: if the walk succeeds, the pattern occurs. A suffix tree is exactly this — a trie of all n suffixes of T, but compressed so that any chain of single-child nodes collapses into one edge labeled with a whole substring. That compression is what keeps it from blowing up: an uncompressed trie of suffixes could have Theta(n^2) nodes, but the compressed tree has at most 2n nodes, because a tree with n leaves and no one-child internal nodes has at most n-1 internal nodes.
Once the tree exists, queries are gorgeous. To test whether pattern P (length p) occurs in T, just walk P down from the root, matching characters along edge labels. If you ever get stuck, P does not occur. If the walk completes, P occurs — and every leaf below the point where you stopped corresponds to one starting position of P in T, so counting occurrences is counting leaves in a subtree, and locating them is listing those leaves. All of this costs O(p + occ), independent of n, the length of the whole text. Read that again: after the one-time build, asking "is this pattern here?" takes time proportional to the pattern, not the text. Searching a billion-character genome for a 20-character probe touches about 20 characters. That is the whole reason to pay for an index.
The honest catch is construction. A suffix tree can be built in O(n) time by clever algorithms (Ukkonen's online construction is the classic), but they are genuinely intricate, and the tree carries a heavy constant: each node needs child pointers and suffix links, so real memory use is often 15 to 40 bytes per character — a real burden on a large text. The linear time bound is true and beautiful, yet "O(n)" hides a fat constant here, the recurring reminder that asymptotics describe scaling, not the bytes your machine actually pays. That memory cost is precisely the discomfort that motivates the next, leaner structure.
Suffix arrays: the same power, much less memory
A suffix array keeps almost all of the suffix tree's query power while throwing away almost all of its bulk. The idea is disarmingly simple: take all n suffixes of T, sort them lexicographically (like dictionary order), and store just the array of their starting positions in sorted order. For "banana$" the sorted suffixes are $, a$, ana$, anana$, banana$, na$, nana$, and the suffix array is the list of their start indices. That is it — one array of n integers, typically 4 bytes each, so about 4n bytes total. No child pointers, no node objects, just a flat array. It is the suffix tree's information squeezed into a list, which is exactly why people reach for it when memory is tight.
Searching uses the array's sortedness. Because the suffixes are in dictionary order, all suffixes that start with pattern P sit in one contiguous block — so binary search over the array finds that block. A plain binary search compares P (length p) against a suffix at each of O(log n) steps, giving O(p log n) per query: a touch slower than the suffix tree's O(p), but usually a fine trade for the enormous memory savings. The block's width is the number of occurrences, and the array entries in it are their locations. To recover the structural shortcuts the suffix tree gave for free, suffix arrays are paired with an LCP array — the longest-common-prefix length between each pair of adjacent sorted suffixes. With the LCP array the binary search sharpens back to O(p + log n), and many tree-style queries become possible on the flat layout.
How fast can the array be built? Sorting n suffixes naively means n comparisons of strings up to length n, an alarming O(n^2 log n). But suffixes overlap heavily, and that redundancy can be exploited: the classic prefix-doubling method sorts by first 1, then 2, then 4, ... characters, reusing previous ranks, to reach O(n log n); and there are linear-time O(n) constructions (the DC3/skew algorithm is the celebrated one). The LCP array can then be built in O(n) by Kasai's algorithm. So in practice a suffix array plus LCP array gives you suffix-tree-grade text indexing in a few integer arrays, at a fraction of the memory — which is why it, not the tree, is the workhorse in real systems from bioinformatics to full-text search.
Choosing your tool, and where the rung leads
Let the question pick the tool. Many patterns, one scan of a streaming text, find them all as they fly by: Aho-Corasick, O(m + n + z). One text you will query over and over with new patterns: build an index once. If you can afford the memory and want the simplest, fastest queries, a suffix tree gives O(p) lookups; if memory matters — and at scale it almost always does — a suffix array with an LCP array gives nearly the same power at roughly a quarter of the footprint. And if the text changes between queries, none of these indices apply cleanly; you are back to the pattern-preprocessing methods of the earlier guides, which read the text fresh each time.
Pattern fixed, text changes -> KMP / Z / Rabin-Karp O(n) per search Many patterns, text scanned once -> Aho-Corasick O(m + n + z) Text fixed, many later queries -> suffix tree build O(n), query O(p + occ) ... same, but memory matters -> suffix array + LCP build O(n log n)/O(n), query O(p log n)
Step back and notice the unifying threads. Aho-Corasick is the failure-function idea of KMP, branched onto a trie — old wisdom carried into a new shape. Suffix trees and arrays both rest on the single observation that substrings are prefixes of suffixes, attacked once with pointers and once with sorting. And every one of these structures is an instance of the same strategic bet you have met throughout this ladder: pay an upfront cost to make a flood of later operations cheap, the very logic behind preprocessing, tries, and indexing in general. The honest caveats also rhyme with the rest of the course — the O(n) build of a suffix tree hides a heavy memory constant, the per-query bounds assume the index is already built, and that +z or +occ term is the unavoidable price of actually producing the answers, not a flaw to optimize away.
That closes the string-and-text rung. From naive matching's honest O(n*m), through KMP's and the Z-algorithm's linear scans, past Rabin-Karp's hashing gamble, to dictionary-wide Aho-Corasick and the suffix-based indices, you now have a toolkit that scales from a single search to a queried-forever corpus. Beyond here lie close relatives worth a later look — the suffix automaton, which recognizes every substring as a tiny finite machine, and sequence alignment, where matching turns approximate and meets the edit-distance dynamic programming from earlier rungs. The same instinct carries through: understand what is fixed, decide what to preprocess, and be honest about what each bound truly buys you.