Lesson · Strings and Pattern Matching · Many patterns, and the text itself

One Pass for Every Word

Four words sharing three character positions become a ten-node trie holding each shared prefix once. Adding failure links turns it into an Aho–Corasick automaton, and one pass over a 22-character text reports all 9 occurrences of all four words for 31 comparisons, where four separate KMP passes cost 98. The output links chain SUFFIXES, not prefixes, which decides which words get reported together and which never do.

Open the interactive lesson Practice

a trie node is a distinct prefix; he, she, his, hers is 10 nodes for 12 characters held as an array per node it is 10 × sigma = 50 cells; as maps, 10 entries prefix query h: he, hers, his — the same three as filtering the list one Aho-Corasick pass: 9 occurrences, 31 comparisons over 22 characters four separate KMP passes on the same text: 98 comparisons output links chain suffixes: position 3 reports she AND he, and nothing else does

One structure for a dictionary, and one scan for all of it

Core ideas

What this lesson establishes

The hard idea is the output link, and it chains suffixes rather than prefixes. The other two are what a trie costs and what one pass buys.

A trie node is a distinct prefix, so sharing is stored once

The words he, she, his, hers have 12 characters between them and the trie has 10 nodes: a root, then h, he, her, hers, hi, his, s, sh, she. The count is one per distinct prefix plus the root, so he being a prefix of hers costs nothing extra. The panel prints the saving as a number — 3 shared character positions — rather than as an adjective, and on a dictionary with no shared prefixes at all it prints 0 and says the trie is separate chains.

Space is two numbers, not one

Holding each node's children in an array indexed by character costs sigma cells per node, whether or not they are used: 10 nodes at sigma 5 is 50 cells. Holding them in a map costs one entry per edge that exists, which is 9. The panel prints both, because the choice between them is the whole space question for a trie and the answer depends on how dense the alphabet is.

An output link follows suffixes, and that is why some words report together

The failure link of a node points to the longest proper suffix of its string that is also a node, and the outputs at a node are its own word plus the words reachable by following failure links. So two words are reported at the same position exactly when one is a suffix of the other: he is a suffix of she, so position 3 of ushers reports both. Prefix nesting does nothing of the kind — with the dictionary a, ab, abc, abcd no position ever reports more than one word, because none of them is a suffix of another.

The material

A trie, its failure links, and one scan for a whole dictionary

The structure and its cost, the prefix query, the automaton, and the suffix relation that decides what is reported together.

Definition · Trie

A trie over a set of words is a rooted tree whose edges carry characters, such that the path from the root to a node spells a distinct prefix of at least one word, and every distinct prefix appears as exactly one node. A node is marked as a word end if the prefix it spells is one of the words. The number of nodes is one plus the number of distinct non-empty prefixes.

Example · Ten nodes for twelve characters

The dictionary is he, she, his, hers. Its distinct non-empty prefixes are h, he, her, hers, hi, his, s, sh and she — nine of them — so the trie has 10 nodes. The four words total 12 characters, and a list of separate strings would store all 12; the trie stores 9 edges, saving the 3 positions where he and hers overlap and where h leads to both he and his.

Held with one array of sigma slots per node that is 10 × 5 = 50 cells, since the dictionary uses the five characters e, h, i, r, s. Held with a map per node it is 9 entries. The panel prints 50 and 10 side by side so the trade is a pair of numbers rather than a preference.

A prefix query walks down from the root and then collects every word-end below. Asking for h returns he, hers and his, and the panel checks that against filtering the word list with a string comparison — the definition of the query, computed a second way.

Definition · Failure and output links

In a trie over a dictionary, the failure link of a node v points to the node spelling the longest proper suffix of v's string that is itself a node of the trie, or to the root if there is none. The outputs of v are v's own word, if it ends one, together with the outputs of v's failure link. The links are computed by a breadth-first traversal, so a node's link is set after every shorter node's.

Theorem · One pass reports every occurrence of every word

Feed the text one character at a time, following the child edge when it exists and otherwise following failure links until a child exists or the root is reached. After reading t[0..i] the current node spells the longest suffix of t[0..i] that is a node of the trie, and its outputs are exactly the dictionary words ending at position i.

By induction on i, exactly as for the single-pattern automaton. Before anything is read the current node is the root, spelling the empty string, which is the longest suffix of the empty text that is a node.

Suppose the current node spells u, the longest suffix of t[0..i−1] that is a node. A node spelling a suffix of t[0..i] of length at least 1 consists of a suffix of t[0..i−1] followed by t[i], and that suffix must itself be a node because every prefix of a node is a node. So the candidates are the nodes w followed by t[i] for w a suffix of u that is a node — which is precisely the failure-link chain from u — and the walk takes the longest.

A word ends at i exactly when it is a suffix of t[0..i], hence a suffix of the current node's string, hence on the failure chain from it. The outputs are defined as that chain's word ends, so they are exactly the words ending at i.

□

The final sentence of that proof is the operative one and it is easy to read past: the words reported together at a position are the ones related by SUFFIX. Not prefix. That distinction is what the lab's last table is for.

One pass against four passes, in comparisons

On the text ushers hers his she he, 22 characters, one pass reports 9 occurrences for 31 comparisons. The four separate KMP passes cost 23, 25, 26 and 24, which is 98 in total — a factor of more than three. The occurrences are he at 2, 7, 17 and 20; she at 1 and 16; his at 12; and hers at 2 and 7.

The saving is not that the automaton is cleverer per character; it is that there is one scan rather than four. Each separate pass reads all 22 characters, so four of them read 88 characters where one reads 22, and that ratio is where the factor of three comes from. With ten words it would be a factor of nearer ten, which is the reason the structure exists.

Which words are reported at the same position

At the end of ushe — text position 3 — the automaton reports both she and he, because he is a suffix of she and so sits on its failure chain. Position 18 does the same. No other position on this text reports two words, and the panel's per-word table is checked against scanning the text separately for each one.

Now take the dictionary a, ab, abc, abcd, where every word is a prefix of the next, and scan abcdabcab. The words end at positions 0, 1, 2 and 3 respectively for the first occurrence, and at no position does the automaton report more than one — because none of bcd, cd, d is a word, so no failure chain from abcd reaches another word end. Prefix nesting is invisible to the output links; only suffix nesting is not.

That is the one property of this structure most likely to be misremembered, and it is checkable in two clicks: the classic dictionary reports two words at one position and the nested one never reports two at all, although the nested one is the one that looks as though it should.

Interactive

A trie, and one pass that finds every word at once

Nodes against array slots, and one scan against one scan per word

Type a dictionary, a prefix, and a text to scan for all of it at once

The trie is drawn from the words you type, with each word-ending node marked. The prefix query is checked against filtering the list, and the single pass is checked word by word against scanning the text separately for each one — the check that catches a failure link pointing at the wrong node.

Worked example

The words, comma separated

Look up every word starting with

The text to scan for all of them at once

Words—

Trie nodes—

Array slots a dense node table would take—

Characters in the words—

Words with that prefix—

Matches, one pass—

Matches, by definition—

Comparisons: one pass against k passes—

Words are separated by commas. A trie stores the shared prefix once, so the node count is the number of DISTINCT prefixes and not the total number of characters — the two KPIs above say how much that saved on these words. Aho-Corasick then adds a failure link to every node, exactly as KMP does to a single pattern, and one pass over the text reports every occurrence of every word. It is checked against scanning the text separately for each one.

Method

Building the trie, then the links, then reading the outputs

Count the nodes before drawing them, and work the failure links out in order of length.

Count nodes as distinct prefixes, not as characters

List every distinct non-empty prefix of every word and add one for the root. For he, she, his, hers that is nine plus one. If the count equals the character total plus one, the words share nothing.

Set the failure links shortest first

A node's link points to the longest proper suffix of its string that is also a node, and finding it uses the links of shorter nodes, so a breadth-first order is not a convenience but a requirement.

Read the outputs as a chain, and ask which words are suffixes

The outputs at a node are its own word plus everything on its failure chain. Two words appear together exactly when one is a suffix of the other, so scan the dictionary for suffix relations before predicting what the scan will report.

Price one pass against k passes in the same unit

One scan reads the text once; k scans read it k times. The panel prints the comparison totals for both — 31 against 98 here — so the claim is a ratio rather than an argument about asymptotics.

Nodes, links, and what reports together

Score 0 / 0

Choose the answer you can justify.

Ten nodes, four failure links that matter, and nine occurrences

The dictionary is he, she, his, hers and the text is ushers hers his she he, 22 characters. Positions are counted from 0.

distinct prefixes h he her hers hi his s sh she = 9 nodes 9 + root = 10 characters in the words 2 + 3 + 3 + 4 = 12 shared positions 12 + 1 - 10 = 3 array slots 10 nodes x sigma 5 = 50 map entries one per edge = 9 failure links that are not the root: she -> he 'he' is the longest suffix of 'she' that is a node sh -> h 'h' is a node outputs at 'she' = { she, he } prefix h he, hers, his by filtering the list: the same 3 occurrences, one pass: he at 2, 7, 17, 20 she at 1, 16 his at 12 hers at 2, 7 total = 9 comparisons, one pass = 31 comparisons, four separate KMP passes 23+25+26+24 = 98 positions reporting two words 3 and 18 ( she and he )

The failure link from she to he is the whole mechanism. Without it the automaton would report she at position 3 and miss the he that ends there, because the scan is at the node for she and never visits the node for he. With it, the outputs at she include everything on its chain, and the 9 occurrences come out right.

For a faded rehearsal, switch the dictionary to a, ab, abc, abcd and the text to abcdabcab. The supplied first move: the trie is a single chain of five nodes, and every failure link points to the root, because no proper suffix of abcd other than the empty string is a node. Predict how many positions report two words — and then check it, because the answer is not what the shape of the dictionary suggests.

Then try he, she, his, hers again with the text sher. Two words ought to be reported and one of them is not the one a left-to-right reading suggests. Give the positions and the words before running it, and say which failure link you used.

Common mistakes

Expecting nested prefixes to report togetherWith a, ab, abc, abcd no position ever reports two words, although every occurrence of abcd contains occurrences of the other three — they simply end at earlier positions. The output chain follows suffixes, so the dictionary that reports together is one like he, she, where the shorter word is the tail of the longer.

Setting failure links in any convenient orderA node's link is found using the links of strictly shorter nodes, so computing them depth-first or in insertion order reads links that have not been set. The breadth-first order is part of the construction, and the symptom of getting it wrong is lost occurrences of one word while every other word still reports correctly — which is what the lab's per-word table is checking.

Quoting one space figure for a trie10 nodes and 50 array slots are both true and they describe different implementations. Which one to quote depends on whether the children are held in a map or an array indexed by character, and on a large alphabet the two differ by orders of magnitude — the panel prints both for that reason.

Check your understanding

✓

Finish when you can build the trie and its links for a dictionary you have not seen and predict which positions report two words.

You should be able to count nodes as distinct prefixes, give both space figures, compute a failure link as a longest-suffix node, explain why the links must be set shortest first, prove that the outputs at a position are the words ending there, and say why suffix nesting and prefix nesting behave completely differently.

Note: Everything up to here preprocesses the PATTERN, or the patterns, and then reads the text once. “The Suffix Array, and What a Sorted Order Answers” turns that round: it preprocesses the text, which is the only way to answer a question about the text that nobody has asked yet — what its longest repeated substring is, or how many distinct substrings it has.