Fast String Searching with the Aho-Corasick Algorithm

mgcadmin 07-08-2026

The Aho-Corasick algorithm is a finite automaton based string match algorithm which is an adaptaion of another well known Finite State Machine based algorithm: The Knuth-Morris-Pratt(KMP) algorithm. While the KMP algorithm uses a DFA & failure function for finding a single pattern, the Aho-Corasick algorithm efficiently finds sets of patterns without needing to backtrack.

The algorithm works by building a prefix trie from the set of keywords to search for, pictured above as the black links connecting nodes. Each node in the trie is then augmented with two additional pointers: a "failure link" pictured in red, and the "output link" (not pictured, they are technically optional). These additional transitions can be efficiently added via breadth first traversal.  The resulting structure is called an Aho-Corsaick Finite Automaton which can be used to find all occurences of the stored keywords in a single pass through a stream of text, and the construction an execution of which is the subject of todays post.

Aho Corsaick at a Glance

When it comes to finding multiple keywords in a body or stream of text you would be very hard pressed to beat this algorithm. It has found its way into programming language standard libraries, the unix tool fgrep, and is the darling of competitive programming participants everywhere. Using a description of the algorithm as laid out in the excercises of the third chapter of the "dragon book" as our guide, we must:

-  define a transition function, g(state, symbol), which maps (state,symbol) pairs to next states, where g(s0, symbol) = s0 where the symbol is not the starting symbol of a keyword. Any symbol which does not have a transition from a state should return a fail state when coming from any state other than the root of the trie.

- define a failure transition function, f(state) which maps (state,fail) to a state in the trie whos prefix shares the longest common suffix with our failed state.

The failure function is computed from the completed prefix trie using the following algorithm:

let s0 be the root of the trie
for each state 's' of depth 1 do:
       f(s) = s0
for each depth (d) >= 1 do:
      for each state (sd) of depth d and symbol (a) where g(sd,a) = s' do:
           s = f(sd)
           while (g(s, a) == NULL) do
                s = f(s);
            f(s') = g(s, a);

Augmented Trie Nodes

There are any number of ways to implement a prefix trie, from adjacency lists/matrices, to parallel arrays, to left child/right sibling trees - and everything in between. I'm going to go with a simple but robust solution of using an unordered_map to associate charachers with child nodes at each state. This allows for the graceful handling of dynamically sized alphabets.

Aside from child pointers, each node will also have pointers for the aformentioned failure and output links. Finally, each node will also cary a set of dictionary indices of the stored patterns which end at the current state.

struct ACNode {
    unordered_map<char,ACNode*> child;
    ACNode* failure;
    ACNode* outlink;
    vector<int> patterns;
    ACNode() {
        failure = nullptr;
        outlink = nullptr;
    }
};

Insertion of a keyword into an AC automaton proceeds identically as it would for a standard prefix-trie. Starting at the root we check to see if the current state has a valid transition on the current symbol. either taking the transition of it exists, or creating one if it does not, and then transitioning to the destination state.

     void insert(string pat) {
            patterns.push_back(pat);
            auto itr = root;
            for (char c : pat) {
                if (itr->child.find(c) == itr->child.end()) {
                    itr->child[c] = new ACNode();
                }
                itr = itr->child[c];
            }
            itr->patterns.push_back(patterns.size()-1);
        }

The last state in a keyword is made into an accepting state by placing the dictionary index of the keyword in that nodes pattern index list.

Once the prefix trie is built, we perform a breadth first (level order) traversal starting from the root node and adding the failure and output links to each state.

Failure Links

The failure links are what allow us to quickly resume searching upon reaching a node with no valid forward trafnsitions without having to back track. This is accomplished by by pointing to a node higher in the automaton that begins a valid suffix of the thus-far-consumed prefix.

We initialize the queue with destination state of every transition on a character from the start state. This first levels failure link is set to point back to the root node explicitly.

      void addFailAndOutLinks() {
            queue<ACNode*> fq;
            for (auto & m : root->child) {
                ACNode* c = m.second;
                c->fail = root;
                fq.push(c);
            }

With our queue primed we continue level by level setting the failure link to point back to the longest common suffix from the current position.

        while (!fq.empty()) {
                auto curr = fq.front(); fq.pop();
                for (auto [ch, child] : curr->child) {
                    ACNode* fail = curr->fail;
                    while (fail != root && fail->child.find(ch) == fail->child.end())
                        fail = fail->fail;
                    child->fail = fail->child.find(ch) == fail->child.end() ? root:fail->child[ch];
                    child->out = (!child->fail->patterns.empty()) ? child->fail:child->fail->out;
                    fq.push(child);
                }
            }
        }

Having set the fail and output links accordingly, g(state, symbol) and f(state) become simple:

       ACNode* g(ACNode* state, char symbol) {
            if (state->child.find(symbol) == state->child.end())
                return nullptr;
            return state->child[symbol];
        }

        ACNode* f(ACNode* state) {
            return state->fail;
        }

Executing the Automaton

Running the resulting automaton on a stream of text is very similar to simulating a DFA. The root of the trie is the start state, and we go character by character step-wise through the text. For each new character we check the current state for a valid transition, using the failure links until we find a legit start state, or end up back at the root node.

        void find(string text) {
            auto s = root;
            int i = 0;
            for (char c : text) {
                while (s != root && g(s, c) == nullptr) {
                    s = f(s);
                }
                s = g(s, c);
                s = (s == nullptr) ? root:s;
                out(s, i++);
            }
        }

Once a valid transition is found, we check to see if the new state is an accepting state, and should it be we announce which strings have been matched by landing on that node.

        void out(ACNode* state, int end) {
            auto itr = state;
            while (itr) {
                for (int idx : itr->patterns) {
                    cout<<"Match at "<<end-patterns[idx].size()+1<<": "<<patterns[idx]<<endl;
                }
                itr = itr->out;
            }
        }

We know a node is accepting if its pattern index list isn't empty. The list holds the dictionary indices of the words accepted by that node, meaning they end at that node, since we know the position in the text the where we encountered the accepting node and we know the length of that word, we can easily calculate the match starting position with a bit of subtraction. The out links serve to connect us to other accepting nodes we crossed in the process of getting to the current one so we can recognize valid strings which are substrings of other valid strings.

---