Aho-Corasick Visualizer

Trie, suffix links and every match of many words.

  • Trie and links
  • Step trace
  • Naive check
A clay tree with a thick trunk and a crown of round clay knots stands on a small round wooden stool, with a coiled clay loop at its foot and two loose clay beads beside it.

The guide

Why one pass over a text can find a whole dictionary of words at once

The Aho-Corasick automaton turns a word list into a trie with extra links, so a text is read once and every word that ends at each position is reported, nested words included.

  • 11 nodes distinct prefixes of seven words; a letter count gives 16
  • 5 of 7 matches of abccab that survive without dictionary links
  • 10 matches a, aa, aaa, aaaa on aaaa, all found by one scan
  • 4 hops suffix links followed while reading the 6 letters of abccab
  • 4,000 of 4,000 seeded random cases where the scan equals a naive search
Read the full guide Fold the guide 8 min · 14 sources

Take seven words, a, ab, bab, bc, bca, c and caa, and the six letters abccab. Where do the words occur? By eye the answer takes a minute: a ends at position 1, ab at 2, then bc and c both end at 3, c again at 4, a at 5 and ab at 6. That is seven matches from six letters, and two of them end on the same letter. The Aho-Corasick algorithm finds all seven by reading each letter exactly once.

One pass instead of one pass per word

The obvious way is the naive one. Test every word at every position of the text and write down the hits. Wikipedia describes the same brute-force idea for a single word, checking the word at each index and comparing character after character. For seven words and six positions that is 42 tests, and each test may compare several letters. With the largest input this page accepts, 50 words and 2,000 letters, it is 100,000 tests.

Alfred Aho and Margaret Corasick published their answer in 1975. It is a dictionary-matching algorithm: it locates every element of a finite set of strings in a text and matches all of them at once. Wikipedia states that its running time is linear in the length of the strings, plus the length of the text, plus the number of matches found.

The National Institute of Standards and Technology entry puts the same point from the other side. Building the machine takes time proportional to the sum of the lengths of the keywords, and the text is then processed in a single pass. The number of transitions the machine makes does not depend on how many keywords there are. More words lengthen the build, not the reading. The trick is to do the work on the words before the text arrives. When the word list is known in advance, Wikipedia notes, the automaton can be built once and kept for later use, which is why the method suits fixed lists such as a computer virus database.

The first step is a trie. A trie stores a set of strings so that each node stands for a prefix: the root is the empty string and every child extends its parent by one character. Wikipedia adds that a trie can be seen as a tree-shaped deterministic finite automaton, one where each state has at most one transition per character.

Count the nodes for the seven words. The words hold 1 + 2 + 3 + 2 + 3 + 1 + 3 = 15 letters, and a careless count gives 15 nodes plus a root, so 16. The trie has only 11 nodes, because the words share prefixes: a is a prefix of ab, b is the start of both bab and bc, and bc is the start of bca. A node exists once for every distinct prefix. The page prints both numbers so that the wrong one is visible.

A trie alone is not enough. Suppose the pointer has followed a-b and the next letter is c. There is no node abc, so a trie would give up and start again from the root. That restart is the backing up that the Knuth-Morris-Pratt algorithm was invented to avoid for one word: after a mismatch the word itself holds enough information to say where the next match could begin, so nothing already read is read again.

Aho and Corasick generalised that idea to a tree. Each node gets a suffix link, which Wikipedia draws as a blue arc. It leads to the node for the longest strict suffix of the node’s path that is itself a node in the trie. For the node ab the strict suffixes are b and the empty string, and b is a node, so ab links to b.

Now the stuck pointer has somewhere to go. At ab with the letter c, it hops to b, asks again, finds that b has a child c, and moves to bc. No letter is read twice. The hop was free in the sense that it needed no new input.

The links are found level by level. Wikipedia describes a breadth-first search from the root, which visits all nodes at one depth before any node at the next. A suffix node is always shallower than the node it serves, so it has been settled by the time it is needed.

For a visited node, take its parent’s suffix link and look for a child there with the same character as the visited node. If there is none, follow the suffix link again and look again, until a child is found or the root is reached. Children of the root link to the root. Doing this for the example gives ten links, one for every node but the root, and seven of them lead to a node other than the root.

The cost of the scan has a neat bound that Wikipedia states only as linear time, and which the page proves for you in small. Every letter moves the pointer down by at most one level, since it takes at most one child. Every hop moves it up by at least one level. The pointer never goes above the root, so the total number of hops cannot exceed the number of letters. That is an aggregate argument of the kind the amortized analysis article describes: the cost of the whole sequence is bounded even though one step may be expensive.

On abccab the pointer makes 4 hops for six letters. The tool counts the hops for any input and checks the bound on 4,000 seeded random cases, where the highest ratio of hops to letters was 0.97. A text of 2,000 letters a with the sixteen words a, aa up to sixteen a’s makes 1,984 hops, which is close to the limit and still under it.

Look again at position 3. The pointer is at bc, which is a word, so bc is reported. But c is a word too, and it ends at position 3 as well, because it is the last letter of bc. A scan that lists only the word at the current node never sees it.

The fix is the dictionary suffix link, drawn green on the Wikipedia page. From each node it leads to the next node that is a dictionary word along the chain of suffix links. From bc it goes straight to c. From bca it skips the non-word ca and lands on a. After each letter the scan reports the word at the current node, if there is one, and then every word along the dictionary links.

Wikipedia’s own illustration of why this matters is the dictionary a, aa, aaa, aaaa on the text aaaa. Multiple matches are returned for one position, and the whole scan finds 10 matches: one a ending at 1, two at 2, three at 3 and four at 4. Switch the dictionary links off on this page and only the word at the current node survives: 4 of the 10, the longest at each position.

The same switch on the main example shows the damage precisely. With dictionary links the scan finds 7 matches. Without them it finds 5 of 7, and the two that vanish are c at 3 and a at 5. Each is a word that ends exactly where a longer word, or a longer prefix of one, also ends.

The other switch is the reset to the root. Turn off the suffix links and a mismatch sends the pointer home. Then the words abc and bcd on the text abcd give only abc: the b that began bcd was read while the pointer was following abc, and the reset forgot it. With the links, the pointer hops from abc to bc, then reads d and reports bcd.

Trying it, and what it leaves out

A second small dictionary shows the same pattern with ordinary words: he, she, his and hers on the text ushers. The trie has 10 nodes where counting letters would give 13. The scan reports she and he, both ending at position 4, and hers at 6. Without dictionary links, he is lost, because it is a suffix of she.

Every figure on the page was recomputed away from the page’s own code. A separate Python script builds the links from their definition, by slicing each path and looking the pieces up, instead of by the breadth-first rule. It also runs the plain naive search. On 4,000 seeded random dictionaries over the letters a, b and c, with up to 6 words of 1 to 4 letters and texts up to 30 letters, the automaton and the naive search found the same pairs of position and word in 4,000 of 4,000 cases. The random generator is the standard seeded one in the Python documentation, so the cases are repeatable.

The algorithm has competitors for the same job. Rabin and Karp’s method hashes the substrings and checks them against a set of hashes; Wikipedia gives its expected time for k patterns of one length as O(n + km), and notes that Aho-Corasick finds all matches of multiple patterns in worst-case time linear in the input length and the number of matches. The Commentz-Walter algorithm borrows from Boyer and Moore to skip ahead; its worst case is O(mn). The choice depends on how many words there are, how long they are and how bad a text may be.

Real tools lean on this. Wikipedia reports that the fgrep variant of grep searches for any of a list of fixed strings using the Aho-Corasick algorithm, and that it formed the basis of the original Unix fgrep.

The page does the heavy parts in a module worker, as the Web Workers documentation describes, so a long text does not freeze the page, and it writes numbers through Intl.NumberFormat. The trie picture is painted on a canvas with rounded rectangles, using the roundRect method.

What the page does not do matters as much. It does not build compressed automata, and it does not handle a word list that grows during the scan; Wikipedia credits Bertrand Meyer with an incremental version for that case. It compares text exactly as typed, with no case folding and no Unicode normalisation, and it takes printable ASCII only. It is a picture of the idea, not a scanning engine, and a very large dictionary needs a different memory layout than the one drawn here.

Sources

Every source consulted for this guide. Links checked November 12, 2026.

  1. Aho-Corasick algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  2. Aho-Corasick - Dictionary of Algorithms and Data Structures NIST (US government)
  3. Trie - Wikipedia Wikipedia (CC BY-SA 4.0)
  4. Knuth-Morris-Pratt algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  5. Deterministic finite automaton - Wikipedia Wikipedia (CC BY-SA 4.0)
  6. Grep - Wikipedia Wikipedia (CC BY-SA 4.0)
  7. Breadth-first search - Wikipedia Wikipedia (CC BY-SA 4.0)
  8. Rabin-Karp algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  9. Commentz-Walter algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  10. Amortized analysis - Wikipedia Wikipedia (CC BY-SA 4.0)
  11. Web Workers API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  12. CanvasRenderingContext2D: roundRect() method - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  13. Intl.NumberFormat - JavaScript | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  14. random - Generate pseudo-random numbers - Python 3.13 documentation Python Software Foundation (PSF License Version 2)