Aho–Corasick: Find Every Keyword in One Pass

Searching for one pattern in a text is a familiar task. Searching for several patterns at the same time is more interesting because the patterns may share prefixes, one pattern may be a suffix of another, and several matches may end at the same text position.

Aho–Corasick is designed for exactly this situation. It combines a trie, which merges shared keyword prefixes, with failure links, which preserve useful partial matches after a mismatch. The resulting search process moves through the text from left to right while reporting every keyword that ends at each position.

This article follows a deliberately small example. The keyword set is:

he
she
hers

The text is:

ushers

The expected matches are:

she  starts at the second character and ends at the fourth
he   starts at the third character and ends at the fourth
hers starts at the third character and ends at the sixth

The matches overlap. she and he end at the same position, and hers begins inside the occurrence of she. A useful multi-pattern search method must preserve all of these possibilities instead of stopping after the first match or discarding shorter matches.

The problem: many keywords, one text​

Suppose a program receives a collection of known words and a long body of text. It needs to report every occurrence of every word, not merely answer whether at least one word appears.

This general task can arise in a document scanner, a keyword highlighter, a text-processing tool, or any system that needs to recognize several known terms while reading text. A result can include the matching keyword, its ending position, and, from the keyword length, its starting position.

A direct strategy would search separately for he, then separately for she, and then separately for hers. That approach repeats work in regions where the patterns are related. The patterns he and hers share the prefix he. The pattern she ends with he. These relationships are useful information, so Aho–Corasick stores them in one combined structure.

The method has two main stages:

1. Build a trie containing all keywords.
2. Add failure links that describe where to continue when the current trie path cannot consume the next text character.

After preparation, the text is scanned from left to right. When a mismatch occurs, the algorithm follows failure links through the keyword structure rather than moving backward through the text and restarting a complete comparison.

A trie merges shared prefixes​

A trie stores strings character by character. Each edge represents one character, and a path from the root represents a prefix of one or more stored keywords.

Insert the three keywords one at a time:

he
she
hers

The resulting structure can be represented informally as follows:

root
├── h
│   └── e   [he]
│       └── r
│           └── s   [hers]
└── s
    └── h
        └── e       [she]

The bracketed nodes are terminal nodes: a complete keyword ends there. The path for he is used directly by hers, so that prefix is represented once in the h branch. The path for she is separate because it begins with s, but its ending letters he will become important when failure links are added.

A trie avoids comparing every keyword from its first character whenever a new text character arrives. If the current state represents her, the structure already records that the latest useful text suffix is her. The algorithm does not need to reconstruct that fact by repeatedly looking backward through the text.

A terminal marker is needed at every node where a complete keyword ends. In this example, the node for he is terminal, the node for she is terminal, and the node for hers is terminal. A node can be terminal and still have children. The node for he is both a complete keyword and a prefix of the longer keyword hers.

This is the first important way Aho–Corasick avoids repeated work: shared prefixes are shared in the trie. The algorithm does not need an independent beginning for every keyword when those beginnings are identical.

Why a trie alone is not enough​

A trie is good at following a matching prefix, but a plain trie does not by itself explain what to do after a mismatch.

Consider the text ushers. After reading us, the useful suffix is s, which is the beginning of she. After reading ush, the suffix sh is a beginning of she. If the algorithm discarded all progress whenever a path failed, it would have to reconsider possible starts in the text.

Aho–Corasick instead uses failure links to retain the longest useful suffix represented in the trie. A failure link connects one trie node to another trie node. Its destination represents the longest proper suffix of the current node's string that is also a prefix of at least one keyword.

For example, the node representing sh has a failure link to the node representing h:

sh -> h

The proper suffixes of sh include h, and h is the beginning of a keyword. It is the longest useful suffix in this case.

The node representing she has a failure link to he:

she -> he

The string he is a suffix of she, and it is also a complete keyword. This link is especially important because reading she has discovered two matches, not one: she and he.

The node representing hers can have a failure link to the node representing s, because the final character of hers is s, and s begins she:

hers -> s

The exact data structure used for edges and outputs can vary, but the purpose of the links remains the same: when the current path cannot be extended, move to a suffix that may still be extended.

Failure links preserve the text pointer​

The phrase one pass refers to movement through the text. The text pointer advances from u to s, then to h, e, r, and s. It does not restart at earlier text positions merely because a trie path failed.

There are two different kinds of movement:

• The text pointer moves forward through the input.
• The current trie state may move through failure links, but this is movement inside the keyword structure, not backward movement through the text.

Suppose the current state represents she and the next character is r. There is no r edge from the she node. Rather than abandoning the recent text, follow the failure link:

she -> he

The node for he does have an r edge because her is the beginning of hers. The algorithm consumes r and reaches her.

The text characters have not been reread. Existing state information has been redirected to a suffix that can continue.

Building failure links conceptually​

Failure links are normally built after the trie exists. The construction processes shallower nodes before deeper nodes because a node's failure destination depends on failure information for a shorter string.

The root is the special starting state. A one-character node such as h or s has no longer proper suffix that is also a useful trie prefix, so its failure destination is the root.

For a deeper node, consider a node representing a string such as sh. Its parent represents s, and the final edge adds h. To find the failure destination for sh, inspect the failure destination of its parent and try to follow the same character h. If that continuation exists, it gives a candidate suffix. If it does not, follow another failure link and try again. Eventually the search reaches the root or finds a transition.

For sh, the useful suffix is h, so:

sh -> h

For she, begin from the failure destination of sh, which is h, and attempt to follow e. The h node has an e child representing he, so:

she -> he

For her, the failure destination of he does not provide a suitable continuation for r, so its link can fall back to the root. For hers, the final s is a useful suffix, producing a link toward the s node.

The construction stage reuses the same suffix logic that the search stage will later use. Preparation turns repeated fallback reasoning into explicit connections in the automaton.

Scanning ushers one character at a time​

Now follow the text from left to right. The root is the initial state.

Reading u​

There is no u branch from the root. The state remains at the root, and no keyword ends here.

The text pointer moves on. There is no separate full search restart at the next character; the automaton simply processes the next input character.

Reading s​

The root has an s edge, so the state becomes the node representing s.

No complete keyword ends here. The state is still meaningful because s is the first character of she.

Reading h​

From s, the h edge exists. The state becomes sh.

No complete keyword ends yet. The state records that the latest useful suffix is sh, a prefix of she.

Reading e​

From sh, the e edge exists. The state becomes she.

The node is terminal, so the algorithm reports:

she

It must not stop there. The failure link from she points to he, and that destination is also terminal. Therefore the same text position reports:

he

At the fourth character, two patterns end. The algorithm discovers both because terminal information is available along the failure chain.

Reading r​

The current state is she. There is no direct r edge from that node. Follow the failure link:

she -> he

The he node has an r edge because the trie contains hers. Follow it and reach her.

No complete keyword ends at r, because her is only a prefix of hers in the supplied keyword set.

The important point is that the text pointer has moved from e to r. The algorithm did not move back to the h in the text and begin a new comparison. The failure link converted the already-known suffix into the beginning of the next possible match.

Reading the final s​

The current state is her, and its s edge exists. Follow it to hers.

The node is terminal, so report:

hers

The complete result is:

she
he
hers

Using one-based character positions in ushers, the matches are:

she  positions 2 through 4
he   positions 3 through 4
hers positions 3 through 6

This tiny example demonstrates several relationships at once. he is a prefix of hers, he is a suffix of she, and all three occurrences overlap in the text.

A state table​

The one-pass behavior is easier to see in a table. The state column names the trie node after each character, and the output column lists every keyword reported at that position.

The transition from she to her deserves special attention. There is no direct r edge from she, so the algorithm follows she -> he and then takes the r edge from he. The table shows only the final state after processing the character, but the failure link explains how that state was reached.

The table also shows why output positions naturally belong to the current text index. Whenever the current node or one of its failure ancestors is terminal, a match ends at the character just consumed.

Reporting every match​

Following a failure link explains the structure, but an implementation also needs a convenient way to report all keywords that end at the current position.

When the state is she, the current node reports she. Its failure destination is he, which reports he. This can be implemented by walking the failure chain whenever a terminal state is reached. Another implementation can store an output collection at each node that includes outputs inherited from its failure destination.

The two designs express the same principle:

• A terminal node reports the keyword ending exactly at that state.
• Failure destinations may represent shorter keywords ending at the same text position.
• Every applicable output must be emitted, not just the longest one.

This matters whenever one keyword is a suffix of another. In this example, reporting only the current node would produce she at the fourth character and miss he. The failure relationship makes the shorter match visible.

The same idea applies if the keyword collection grows. If another keyword ended at a suffix of hers, reaching the hers state could report both the long word and the shorter suffix, provided that the suffix is represented by the failure chain or inherited output data.

Output handling is part of the definition of finding every keyword. Detecting only the first terminal state is not yet complete multi-pattern matching.

Match positions and lengths​

Aho–Corasick naturally identifies an ending position. If the keyword length is known, the starting position follows from a simple calculation.

For example, hers has length four and ends at position six in ushers. With one-based positions:

Thus, hers occupies positions three through six. The same calculation places she at positions two through four and he at positions three through four.

The search structure does not need to rescan those characters to determine the locations. A terminal node can store the keyword identity and length, and the search can calculate the location when that node is reported.

A terminal output can also carry application-specific information, such as a dictionary identifier, a category, or a label. The example only requires reporting the matching words, but the same output mechanism can associate additional metadata with each keyword.

What repeated work is avoided?​

Aho–Corasick avoids repeated work in several connected ways.

Shared prefixes are stored once​

The trie merges common beginnings. If several keywords begin with the same sequence, that sequence is represented by one path rather than rebuilt independently for each keyword.

For he and hers, the path h followed by e is shared. Once the scan reaches he, the structure already knows that it has reached the end of one keyword and the beginning of a longer one.

Failed comparisons do not restart the text scan​

A mismatch does not force the text pointer to move backward. The state changes through failure links, while the next text character is consumed in forward order.

In ushers, the state she cannot accept r, but its suffix he can. A failure link makes that transition available without reconsidering earlier characters.

Suffix relationships are explicit​

The string he appears as the ending of she. The failure link she -> he records that relationship. A match ending at the current position can therefore produce multiple outputs without searching the same ending again from scratch.

The state summarizes recent history​

The current trie node represents the longest useful suffix of the text read so far among the prefixes represented by the keyword set. That summary allows the algorithm to continue from the current input position instead of reconstructing all possible partial matches.

The phrase longest useful suffix is important. The algorithm is not storing every arbitrary substring. It stores the suffix that can matter for continuing a known keyword, while failure links provide access to shorter useful suffixes when necessary.

A conceptual search routine​

The roles of trie transitions, failure links, and outputs can be shown in pseudocode:

state = root
for each character c in the text:
    while state has no edge labeled c and state is not root:
        state = failure[state]
    if state has an edge labeled c:
        state = that child
    else:
        state = root
    report outputs associated with state and its failure ancestors

The loop consumes text characters in order. The while step changes only the trie state. The output step ensures that shorter suffix keywords are not lost.

At the root, if no transition exists for the current character, the state remains at the root. If the root has an edge for that character, the state follows it. This makes returning to the root a normal part of the same scan rather than a separate search restart.

Overlapping matches are normal​

Many search approaches need explicit care when matches overlap. In Aho–Corasick, overlap is a natural consequence of continuing from the current state and inspecting failure outputs.

In ushers, she covers positions two through four. he covers positions three through four, so it overlaps she. hers covers positions three through six, so it overlaps both.

Nothing is removed from the text, and the scan does not jump past a completed word. After reporting she and he at the fourth character, it still processes r and s. That is how it discovers hers.

This distinction matters when an application wants every occurrence rather than only non-overlapping occurrences. The matcher should preserve all matches first. If an application later wants non-overlapping results, it can apply its own filtering policy to the reported ranges.

Practical use: keyword detection​

A multi-pattern matcher is useful whenever an application has a known set of terms and wants to inspect incoming text. The keyword set might represent labels, names, commands, or phrases relevant to the application.

Aho–Corasick combines those keywords into one structure. As text arrives, the current state moves through the combined trie and emits matches as they end. An application can process each output immediately or store the results for later display and analysis.

For example, each terminal node can be associated with a category. When the state reaches she, the output mechanism can emit both the record for she and the record for he. The matching structure identifies the occurrences; the application decides what those occurrences mean and how to handle them.

This separation is useful in text search. The matcher can remain focused on character transitions and locations, while higher-level code handles highlighting, classification, replacement, or reporting.

Practical use: search boxes and autocomplete​

A search box often needs to recognize terms while the user types. A trie is naturally useful when the application has a fixed collection of labels, tags, or known terms organized by prefix. Aho–Corasick becomes especially relevant when the current input must be checked against many known keywords and multiple occurrences must be reported.

As each new character arrives, the application can inspect the current outputs and update its interface. If the input is ushers, the matcher can report the ranges for she, he, and hers. The interface can then choose whether to display all overlapping highlights, prefer one result, or apply another presentation rule.

Autocomplete itself may focus primarily on finding candidates that begin with the user's current prefix. Aho–Corasick addresses a broader scanning problem: recognizing many complete keywords while reading an entire text. The trie provides shared beginnings, and failure links add the suffix-aware continuation required for one-pass multi-pattern matching.

The distinction is practical. Use the structure that matches the question being asked. A prefix-oriented interface may mainly need trie navigation, while a text scanner that must find every occurrence benefits from failure links and output reporting.

Practical use: processing text in chunks​

The one-pass model also fits text that arrives as a sequence of characters rather than as one complete string. The current state can be retained between chunks.

A keyword may begin near the end of one chunk and finish at the beginning of the next. If the current trie state is preserved, the next character can continue the partial match. The important idea is that the state summarizes the recent useful suffix, so the next chunk does not need to start from the root merely because a chunk boundary occurred.

The application must decide how to represent positions across chunks and how to store output records. Those are integration choices. The matching principle stays the same: consume characters in order, follow trie transitions and failure links, and emit terminal outputs.

Construction and search are separate responsibilities​

A useful design separates preparation from scanning.

During construction, the system receives the keyword collection, creates trie nodes, marks terminal nodes, and connects failure links. This is the stage where relationships among the keywords are discovered.

During search, the system receives the text and maintains one current state. For each character, it follows a matching edge if one exists. Otherwise, it follows failure links until a matching edge is available or the root is reached. It then advances to the next text character and reports outputs for the resulting state.

This separation is practical when the same keyword collection is used against many texts. The keyword structure can be prepared once and reused for each new input. The exact storage format for edges, failure links, and outputs can be selected according to the application.

It also makes testing easier. Trie construction can be tested with a few keyword sets, failure-link construction can be checked against expected suffix relationships, and scanning can be tested with texts containing overlaps and mismatches.

Trade-offs​

Aho–Corasick exchanges repeated search work for a combined keyword structure that must be built and stored.

The trie requires memory for nodes, edges, terminal markers, and failure links. The amount of structure depends on the total keyword content and on how much prefix sharing exists. Strongly shared prefixes can make the combined representation attractive, while keywords with little sharing still require their distinct paths.

Failure-link output handling also affects storage and processing. If every node stores inherited outputs, reporting can be convenient, but output information may be duplicated across nodes. If the implementation walks failure chains at match time, the structure may avoid some duplicated output storage, but output discovery follows those links during scanning. The appropriate choice depends on the application's needs and on how many outputs can end at one position.

The result set itself can be large. If many keywords end at many text positions, recording every match requires space for those records regardless of how the automaton finds them. An application that only needs to trigger an event can process outputs immediately instead of retaining the complete list.

The method is most compelling when there are multiple patterns to search for and the patterns are searched together or reused. For one very short keyword, a simpler matcher may be easier to implement. Aho–Corasick earns its structural complexity when shared prefixes, suffix relationships, overlapping occurrences, and one-pass reporting matter.

Common implementation mistakes​

Reporting only the current node​

When the state reaches she, reporting only she misses he. Always account for terminal failure ancestors or store inherited output information.

Stopping after a match​

A completed keyword does not mean the text scan is finished. In ushers, the scan must continue after finding she and he to discover hers.

Moving the text pointer backward​

Failure links are not instructions to reread earlier text characters. They are transitions inside the trie. The input pointer should continue forward.

Treating a terminal node as a dead end​

The node for he is terminal but also leads to hers. A keyword can be both a complete match and a prefix of a longer keyword. Terminal status should not prevent further transitions.

Ignoring overlapping outputs​

Overlaps are expected. The same ending position can report multiple keywords, and a later keyword can begin before an earlier one has finished. Do not discard results unless the application explicitly requests a non-overlapping policy.

Forgetting root behavior​

When no transition exists and no failure link can help, return to the root and continue with the same current character. That character may itself begin a new keyword path.

A mental model​

A useful way to remember Aho–Corasick is to view the trie as a map of promising prefixes and failure links as shortcuts between promising suffixes.

The trie answers this question: if the current useful suffix is represented by this node, can the next character extend it?

A failure link answers a second question: if it cannot, what shorter suffix might still be a useful prefix?

The output information answers the final question: which keywords end at the current position, including keywords represented by suffix states?

For ushers, the important state progression is:

root --s--> s --h--> sh --e--> she
                         failure to he
she --failure--> he --r--> her --s--> hers

This is not a sequence of separate text passes. It is one sequence of input characters with state changes inside the keyword graph. The word she is recognized, its suffix he is recognized through failure information, and the state then continues toward hers.

Final takeaways​

Aho–Corasick finds every occurrence of many keywords by combining three ideas.

First, a trie merges shared prefixes. The keywords he and hers share the path he, while she contributes another path whose suffix connects to he.

Second, failure links preserve useful suffixes after a mismatch. The link she -> he means that reaching she also reveals the shorter keyword he. The same link lets the next character r continue toward her and then hers.

Third, output reporting follows terminal nodes and their failure relationships. This turns one state at one text position into possibly several matching keywords.

For the text ushers and the patterns he, she, and hers, the scan reports:

she  at positions 2–4
he   at positions 3–4
hers at positions 3–6

The text is consumed from left to right. The algorithm does not restart a complete comparison for every keyword or move backward through the input after a mismatch. Instead, the trie records shared beginnings, failure links record useful suffixes, and terminal outputs preserve every match, including overlapping ones.

That combination is the practical strength of Aho–Corasick: prepare one keyword structure, scan the text once, and let the links carry already-known information forward.