C++ Programming for Aho-Corasick Algorithm for Pattern Searching

Given an input text and an array of k words, arr[], find all occurrences of all words in the input text. Let n be the length of text and m be the total number characters in all words, i.e. m = length(arr[0]) + length(arr[1]) + .. + O(n + length(arr[k-1]). Here k is total numbers of input words.

Example:

Input: text = "ahishers"    
       arr[] = {"he", "she", "hers", "his"}

Output:
   Word his appears from 1 to 3
   Word he appears from 4 to 5
   Word she appears from 3 to 5
   Word hers appears from 4 to 7

If we use a linear time searching algorithm like KMP, then we need to one by one search all words in text[]. This gives us total time complexity as O(n + length(word[0]) + O(n + length(word[1]) + O(n + length(word[2]) + … O(n + length(word[k-1]). This time complexity can be written as O(n*k + m).
Aho-Corasick Algorithm finds all words in O(n + m + z) time where z is total number of occurrences of words in text. The Aho–Corasick string matching algorithm formed the basis of the original Unix command fgrep.

1. Prepocessing : Build an automaton of all words in arr[] The automaton has mainly three functions:

   1. Go To :   This function simply follows edges
                of Trie of all words in arr[]. It is
                represented as 2D array g[][] where
                we store next state for current state 
                and character.
      
      Failure : This function stores all edges that are
                followed when current character doesn't
                have edge in Trie.  It is represented as
                1D array f[] where we store next state for
                current state. 
      
      Output :  Stores indexes of all words that end at 
                current state. It is represented as 1D 
                array o[] where we store indexes
                of all matching words as a bitmap for 
                current state.
      

   2. Matching : Traverse the given text over built automaton to find all matching words.

[ad type=”banner”]

1. Preprocessing:
   1. We first Build a Trie (or Keyword Tree) of all words.
   2. Next we extend Trie into an automaton to support linear time matching.

Go to :
We build Trie. And for all characters which don’t have an edge at root, we add an edge back to root.

Failure :
For a state s, we find the longest proper suffix which is a proper prefix of some pattern. This is done using Breadth First Traversal of Trie.

Output :
For a state s, indexes of all words ending at s are stored. These indexes are stored as bitwise map (by doing bitwise OR of values). This is also computing using Breadth First Traversal with Failure.

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20implementation%20of%20Aho%20Corasick%20algorithm%0A%2F%2F%20for%20string%20matching%0Ausing%20namespace%20std%3B%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0A%20%0A%2F%2F%20Max%20number%20of%20states%20in%20the%20matching%20machine.%0A%2F%2F%20Should%20be%20equal%20to%20the%20sum%20of%20the%20length%20of%20all%20keywords.%0Aconst%20int%20MAXS%20%3D%20500%3B%0A%20%0A%2F%2F%20Maximum%20number%20of%20characters%20in%20input%20alphabet%0Aconst%20int%20MAXC%20%3D%2026%3B%0A%20%0A%2F%2F%20OUTPUT%20FUNCTION%20IS%20IMPLEMENTED%20USING%20out%5B%5D%0A%2F%2F%20Bit%20i%20in%20this%20mask%20is%20one%20if%20the%20word%20with%20index%20i%0A%2F%2F%20appears%20when%20the%20machine%20enters%20this%20state.%0Aint%20out%5BMAXS%5D%3B%0A%20%0A%2F%2F%20FAILURE%20FUNCTION%20IS%20IMPLEMENTED%20USING%20f%5B%5D%0Aint%20f%5BMAXS%5D%3B%0A%20%0A%2F%2F%20GOTO%20FUNCTION%20(OR%20TRIE)%20IS%20IMPLEMENTED%20USING%20g%5B%5D%5B%5D%0Aint%20g%5BMAXS%5D%5BMAXC%5D%3B%0A%20%0A%2F%2F%20Builds%20the%20string%20matching%20machine.%0A%2F%2F%20arr%20-%20%20%20array%20of%20words.%20The%20index%20of%20each%20keyword%20is%20important%3A%0A%2F%2F%20%20%20%20%20%20%20%20%20%22out%5Bstate%5D%20%26%20(1%20%3C%3C%20i)%22%20is%20%3E%200%20if%20we%20just%20found%20word%5Bi%5D%0A%2F%2F%20%20%20%20%20%20%20%20%20in%20the%20text.%0A%2F%2F%20Returns%20the%20number%20of%20states%20that%20the%20built%20machine%20has.%0A%2F%2F%20States%20are%20numbered%200%20up%20to%20the%20return%20value%20-%201%2C%20inclusive.%0Aint%20buildMatchingMachine(string%20arr%5B%5D%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20all%20values%20in%20output%20function%20as%200.%0A%20%20%20%20memset(out%2C%200%2C%20sizeof%20out)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20all%20values%20in%20goto%20function%20as%20-1.%0A%20%20%20%20memset(g%2C%20-1%2C%20sizeof%20g)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initially%2C%20we%20just%20have%20the%200%20state%0A%20%20%20%20int%20states%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Construct%20values%20for%20goto%20function%2C%20i.e.%2C%20fill%20g%5B%5D%5B%5D%0A%20%20%20%20%2F%2F%20This%20is%20same%20as%20building%20a%20Trie%20for%20arr%5B%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20k%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20const%20string%20%26word%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20int%20currentState%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Insert%20all%20characters%20of%20current%20word%20in%20arr%5B%5D%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20word.size()%3B%20%2B%2Bj)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20ch%20%3D%20word%5Bj%5D%20-%20’a’%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Allocate%20a%20new%20node%20(create%20a%20new%20state)%20if%20a%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20node%20for%20ch%20doesn’t%20exist.%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(g%5BcurrentState%5D%5Bch%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20g%5BcurrentState%5D%5Bch%5D%20%3D%20states%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20currentState%20%3D%20g%5BcurrentState%5D%5Bch%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Add%20current%20word%20in%20output%20function%0A%20%20%20%20%20%20%20%20out%5BcurrentState%5D%20%7C%3D%20(1%20%3C%3C%20i)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20For%20all%20characters%20which%20don’t%20have%20an%20edge%20from%0A%20%20%20%20%2F%2F%20root%20(or%20state%200)%20in%20Trie%2C%20add%20a%20goto%20edge%20to%20state%0A%20%20%20%20%2F%2F%200%20itself%0A%20%20%20%20for%20(int%20ch%20%3D%200%3B%20ch%20%3C%20MAXC%3B%20%2B%2Bch)%0A%20%20%20%20%20%20%20%20if%20(g%5B0%5D%5Bch%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20g%5B0%5D%5Bch%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Now%2C%20let’s%20build%20the%20failure%20function%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20values%20in%20fail%20function%0A%20%20%20%20memset(f%2C%20-1%2C%20sizeof%20f)%3B%0A%20%0A%20%20%20%20%2F%2F%20Failure%20function%20is%20computed%20in%20breadth%20first%20order%0A%20%20%20%20%2F%2F%20using%20a%20queue%0A%20%20%20%20queue%3Cint%3E%20q%3B%0A%20%0A%20%20%20%20%20%2F%2F%20Iterate%20over%20every%20possible%20input%0A%20%20%20%20for%20(int%20ch%20%3D%200%3B%20ch%20%3C%20MAXC%3B%20%2B%2Bch)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20All%20nodes%20of%20depth%201%20have%20failure%20function%20value%0A%20%20%20%20%20%20%20%20%2F%2F%20as%200.%20For%20example%2C%20in%20above%20diagram%20we%20move%20to%200%0A%20%20%20%20%20%20%20%20%2F%2F%20from%20states%201%20and%203.%0A%20%20%20%20%20%20%20%20if%20(g%5B0%5D%5Bch%5D%20!%3D%200)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20f%5Bg%5B0%5D%5Bch%5D%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20q.push(g%5B0%5D%5Bch%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Now%20queue%20has%20states%201%20and%203%0A%20%20%20%20while%20(q.size())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Remove%20the%20front%20state%20from%20queue%0A%20%20%20%20%20%20%20%20int%20state%20%3D%20q.front()%3B%0A%20%20%20%20%20%20%20%20q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20For%20the%20removed%20state%2C%20find%20failure%20function%20for%0A%20%20%20%20%20%20%20%20%2F%2F%20all%20those%20characters%20for%20which%20goto%20function%20is%0A%20%20%20%20%20%20%20%20%2F%2F%20not%20defined.%0A%20%20%20%20%20%20%20%20for%20(int%20ch%20%3D%200%3B%20ch%20%3C%3D%20MAXC%3B%20%2B%2Bch)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20goto%20function%20is%20defined%20for%20character%20’ch’%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20’state’%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(g%5Bstate%5D%5Bch%5D%20!%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20failure%20state%20of%20removed%20state%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20failure%20%3D%20f%5Bstate%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20the%20deepest%20node%20labeled%20by%20proper%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20suffix%20of%20string%20from%20root%20to%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20state.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(g%5Bfailure%5D%5Bch%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20failure%20%3D%20f%5Bfailure%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20failure%20%3D%20g%5Bfailure%5D%5Bch%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%5Bg%5Bstate%5D%5Bch%5D%5D%20%3D%20failure%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Merge%20output%20values%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20out%5Bg%5Bstate%5D%5Bch%5D%5D%20%7C%3D%20out%5Bfailure%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Insert%20the%20next%20level%20node%20(of%20Trie)%20in%20Queue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q.push(g%5Bstate%5D%5Bch%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20states%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20the%20next%20state%20the%20machine%20will%20transition%20to%20using%20goto%0A%2F%2F%20and%20failure%20functions.%0A%2F%2F%20currentState%20-%20The%20current%20state%20of%20the%20machine.%20Must%20be%20between%0A%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%200%20and%20the%20number%20of%20states%20-%201%2C%20inclusive.%0A%2F%2F%20nextInput%20-%20The%20next%20character%20that%20enters%20into%20the%20machine.%0Aint%20findNextState(int%20currentState%2C%20char%20nextInput)%0A%7B%0A%20%20%20%20int%20answer%20%3D%20currentState%3B%0A%20%20%20%20int%20ch%20%3D%20nextInput%20-%20’a’%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20goto%20is%20not%20defined%2C%20use%20failure%20function%0A%20%20%20%20while%20(g%5Banswer%5D%5Bch%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20answer%20%3D%20f%5Banswer%5D%3B%0A%20%0A%20%20%20%20return%20g%5Banswer%5D%5Bch%5D%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20finds%20all%20occurrences%20of%20all%20array%20words%0A%2F%2F%20in%20text.%0Avoid%20searchWords(string%20arr%5B%5D%2C%20int%20k%2C%20string%20text)%0A%7B%0A%20%20%20%20%2F%2F%20Preprocess%20patterns.%0A%20%20%20%20%2F%2F%20Build%20machine%20with%20goto%2C%20failure%20and%20output%20functions%0A%20%20%20%20buildMatchingMachine(arr%2C%20k)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20current%20state%0A%20%20%20%20int%20currentState%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20text%20through%20the%20nuilt%20machine%20to%20find%0A%20%20%20%20%2F%2F%20all%20occurrences%20of%20words%20in%20arr%5B%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20text.size()%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20currentState%20%3D%20findNextState(currentState%2C%20text%5Bi%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20match%20not%20found%2C%20move%20to%20next%20state%0A%20%20%20%20%20%20%20%20if%20(out%5BcurrentState%5D%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20continue%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Match%20found%2C%20print%20all%20matching%20words%20of%20arr%5B%5D%0A%20%20%20%20%20%20%20%20%2F%2F%20using%20output%20function.%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20k%3B%20%2B%2Bj)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(out%5BcurrentState%5D%20%26%20(1%20%3C%3C%20j))%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Word%20%22%20%3C%3C%20arr%5Bj%5D%20%3C%3C%20%22%20appears%20from%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20i%20-%20arr%5Bj%5D.size()%20%2B%201%20%3C%3C%20%22%20to%20%22%20%3C%3C%20i%20%3C%3C%20endl%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%0Aint%20main()%0A%7B%0A%20%20%20%20string%20arr%5B%5D%20%3D%20%7B%22he%22%2C%20%22she%22%2C%20%22hers%22%2C%20%22his%22%7D%3B%0A%20%20%20%20string%20text%20%3D%20%22ahishers%22%3B%0A%20%20%20%20int%20k%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%0A%20%20%20%20searchWords(arr%2C%20k%2C%20text)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”C++” highlight=”” provider=”manual”/]

Output:

Word his appears from 1 to 3
Word he appears from 4 to 5
Word she appears from 3 to 5
Word hers appears from 4 to 7

[ad type=”banner”]