{"id":25546,"date":"2017-10-15T20:06:44","date_gmt":"2017-10-15T14:36:44","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25546"},"modified":"2017-10-15T20:06:44","modified_gmt":"2017-10-15T14:36:44","slug":"c-programming-for-aho-corasick-algorithm-pattern-searching","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-for-aho-corasick-algorithm-pattern-searching\/","title":{"rendered":"C++ Programming for Aho-Corasick Algorithm for Pattern Searching"},"content":{"rendered":"

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.<\/p>\n

Example:<\/strong><\/p>\n

Input: text = \"ahishers\"    \r\n       arr[] = {\"he\", \"she\", \"hers\", \"his\"}\r\n\r\nOutput:\r\n   Word his<\/strong> appears from 1 to 3\r\n   Word he<\/strong> appears from 4 to 5\r\n   Word she<\/strong> appears from 3 to 5\r\n   Word hers<\/strong> appears from 4 to 7<\/pre>\n
If we use a linear time searching algorithm like KMP<\/strong>, 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]) + \u2026 O(n + length(word[k-1]). This time complexity can be written as O(n*k + m)<\/strong><\/em>.
\nAho-Corasick Algorithm<\/strong> finds all words in O(n + m + z)<\/strong><\/em> time where z <\/strong>is total number of occurrences of words in text. The Aho\u2013Corasick string matching algorithm formed the basis of the original Unix command fgrep.<\/p>\n
    \n
  1. Prepocessing : <\/strong>Build an automaton of all words in arr[] The automaton has mainly three functions:\n
      \n
    1. \n
      Go To :   This function simply follows edges\r\n          of Trie of all words in arr[]. It is\r\n          represented as 2D array g[][] <\/strong>where\r\n          we store next state for current state \r\n          and character.\r\n\r\nFailure : This function stores all edges that are\r\n          followed when current character doesn't\r\n          have edge in Trie.  It is represented as\r\n          1D array f[]<\/strong> where we store next state for\r\n          current state. \r\n\r\nOutput :  Stores indexes of all words that end at \r\n          current state. It is represented as 1D \r\n          array o[]<\/strong> where we store indexes\r\n          of all matching words as a bitmap for \r\n          current state.\r\n<\/pre>\n<\/li>\n
    2. Matching :<\/strong> Traverse the given text over built automaton to find all matching words.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n[ad type=\u201dbanner\u201d]\n
        \n
      1. Preprocessing:<\/strong>\n
          \n
        1. We first Build a Trie<\/a> (or Keyword Tree) of all words.\"C++<\/li>\n
        2. Next we extend Trie into an automaton to support linear time matching.\"Next<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
          Go to :
          \nWe build Trie. And for all characters which don\u2019t have an edge at root, we add an edge back to root.<\/p>\n
          Failure :
          \nFor 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.<\/p>\n
          Output :
          \nFor 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.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u2019a\u2019%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\u2019t%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\u2019t%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\u2019s%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\u2019ch\u2019%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20\u2019state\u2019%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\u2019a\u2019%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\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
          Output:<\/p>\n
          Word his appears from 1 to 3\r\nWord he appears from 4 to 5\r\nWord she appears from 3 to 5\r\nWord hers appears from 4 to 7<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
          C++ Programming for Aho-Corasick Algorithm for Pattern Searching – Searching and sorting – Aho-Corasick Algorithm finds all words in O(n + m + z) time.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,71670],"tags":[73836,73838,72306,73832,73273,73822,73322,73827,73851,73843,73848,73840,73835,73826,73315,73844,73852,73846,73830,73222,73833,73834,73850,73824,73855,73192,73270,73600,73274,73829,73847,73823,73858,70097,73841,73188],"class_list":["post-25546","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-searching-and-sorting","tag-aho-streaming","tag-algorithm-animation-visualization","tag-algorithm-visualization","tag-bca-dictionary","tag-best-pattern-matching-algorithm","tag-bfs-geeksforgeeks","tag-boyer-moore-pattern-matching-algorithm-example","tag-cashew","tag-david-barber","tag-david-machine","tag-deep-learning-time-series","tag-deep-packet-inspection-open-source","tag-dictionary-match","tag-hotmail","tag-implementation-of-algorithm-in-c","tag-intrusion-detection-and-prevention-systems","tag-javascript-search-string","tag-julia-machine-learning","tag-keyword-matching-algorithm","tag-kmp-string-matching-algorithm","tag-link-dictionary","tag-machine-learning-string-matching","tag-machine-learning-time-series","tag-match-dictionary","tag-matching-engine","tag-naive-string-matching-algorithm","tag-pattern-matching-algorithm","tag-pattern-matching-algorithm-for-intrusion-detection-system","tag-pattern-matching-algorithm-ppt","tag-pdf-splitter-offline","tag-phonetic-search","tag-search-animation","tag-search-string-in-javascript","tag-searching-algorithms-in-c","tag-selenium-documentation-pdf","tag-string-match"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25546","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25546"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25546\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25546"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25546"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25546"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}