\/\/ C++ program for implementation of Aho Corasick algorithm\/\/ for string matchingusing namespace std;#include <bits\/stdc++.h> \/\/ Max number of states in the matching machine.\/\/ Should be equal to the sum of the length of all keywords.const int MAXS = 500; \/\/ Maximum number of characters in input alphabetconst int MAXC = 26; \/\/ OUTPUT FUNCTION IS IMPLEMENTED USING out[]\/\/ Bit i in this mask is one if the word with index i\/\/ appears when the machine enters this state.int out[MAXS]; \/\/ FAILURE FUNCTION IS IMPLEMENTED USING f[]int f[MAXS]; \/\/ GOTO FUNCTION (OR TRIE) IS IMPLEMENTED USING g[][]int g[MAXS][MAXC]; \/\/ Builds the string matching machine.\/\/ arr - array of words. The index of each keyword is important:\/\/ "out[state] & (1 << i)" is > 0 if we just found word[i]\/\/ in the text.\/\/ Returns the number of states that the built machine has.\/\/ States are numbered 0 up to the return value - 1, inclusive.int buildMatchingMachine(string arr[], int k){ \/\/ Initialize all values in output function as 0. memset(out, 0, sizeof out); \/\/ Initialize all values in goto function as -1. memset(g, -1, sizeof g); \/\/ Initially, we just have the 0 state int states = 1; \/\/ Construct values for goto function, i.e., fill g[][] \/\/ This is same as building a Trie for arr[] for (int i = 0; i < k; ++i) { const string &word = arr[i]; int currentState = 0; \/\/ Insert all characters of current word in arr[] for (int j = 0; j < word.size(); ++j) { int ch = word[j] - 'a'; \/\/ Allocate a new node (create a new state) if a \/\/ node for ch doesn't exist. if (g[currentState][ch] == -1) g[currentState][ch] = states++; currentState = g[currentState][ch]; } \/\/ Add current word in output function out[currentState] |= (1 << i); } \/\/ For all characters which don't have an edge from \/\/ root (or state 0) in Trie, add a goto edge to state \/\/ 0 itself for (int ch = 0; ch < MAXC; ++ch) if (g[0][ch] == -1) g[0][ch] = 0; \/\/ Now, let's build the failure function \/\/ Initialize values in fail function memset(f, -1, sizeof f); \/\/ Failure function is computed in breadth first order \/\/ using a queue queue<int> q; \/\/ Iterate over every possible input for (int ch = 0; ch < MAXC; ++ch) { \/\/ All nodes of depth 1 have failure function value \/\/ as 0. For example, in above diagram we move to 0 \/\/ from states 1 and 3. if (g[0][ch] != 0) { f[g[0][ch]] = 0; q.push(g[0][ch]); } } \/\/ Now queue has states 1 and 3 while (q.size()) { \/\/ Remove the front state from queue int state = q.front(); q.pop(); \/\/ For the removed state, find failure function for \/\/ all those characters for which goto function is \/\/ not defined. for (int ch = 0; ch <= MAXC; ++ch) { \/\/ If goto function is defined for character 'ch' \/\/ and 'state' if (g[state][ch] != -1) { \/\/ Find failure state of removed state int failure = f[state]; \/\/ Find the deepest node labeled by proper \/\/ suffix of string from root to current \/\/ state. while (g[failure][ch] == -1) failure = f[failure]; failure = g[failure][ch]; f[g[state][ch]] = failure; \/\/ Merge output values out[g[state][ch]] |= out[failure]; \/\/ Insert the next level node (of Trie) in Queue q.push(g[state][ch]); } } } return states;} \/\/ Returns the next state the machine will transition to using goto\/\/ and failure functions.\/\/ currentState - The current state of the machine. Must be between\/\/ 0 and the number of states - 1, inclusive.\/\/ nextInput - The next character that enters into the machine.int findNextState(int currentState, char nextInput){ int answer = currentState; int ch = nextInput - 'a'; \/\/ If goto is not defined, use failure function while (g[answer][ch] == -1) answer = f[answer]; return g[answer][ch];} \/\/ This function finds all occurrences of all array words\/\/ in text.void searchWords(string arr[], int k, string text){ \/\/ Preprocess patterns. \/\/ Build machine with goto, failure and output functions buildMatchingMachine(arr, k); \/\/ Initialize current state int currentState = 0; \/\/ Traverse the text through the nuilt machine to find \/\/ all occurrences of words in arr[] for (int i = 0; i < text.size(); ++i) { currentState = findNextState(currentState, text[i]); \/\/ If match not found, move to next state if (out[currentState] == 0) continue; \/\/ Match found, print all matching words of arr[] \/\/ using output function. for (int j = 0; j < k; ++j) { if (out[currentState] & (1 << j)) { cout << "Word " << arr[j] << " appears from " << i - arr[j].size() + 1 << " to " << i << endl; } } }} \/\/ Driver program to test aboveint main(){ string arr[] = {"he", "she", "hers", "his"}; string text = "ahishers"; int k = sizeof(arr)\/sizeof(arr[0]); searchWords(arr, k, text); return 0;}<\/code><\/pre> <\/div>\nOutput:<\/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=”banner”]\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}]}}
![\"C++](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/aho-corasick1.png\")
<\/li>\n![\"Next](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/aho-corasick2-660x379.png\")
<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n