Users Online

· Guests Online: 43

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads
No Threads created
Hottest Threads
No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Articles Hierarchy

Articles Home » C++ » C++ Program to Implement Aho-Corasick Algorithm for Pattern Searching

C++ Program to Implement Aho-Corasick Algorithm for Pattern Searching

C++ Program to Implement Aho-Corasick Algorithm for Pattern Searching

 

 

In computer science, the Aho–Corasick string matching algorithm is a string searching algorithm, it is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the “dictionary”) within an input text. It matches all patterns simultaneously. The complexity of the algorithm is linear in the length of the patterns plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa).

 

Here is source code of the C++ Program to Implement Aho-Corasick Algorithm for String Matching. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. using namespace std;
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <numeric>
  6. #include <sstream>
  7. #include <fstream>
  8. #include <cassert>
  9. #include <climits>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <string>
  13. #include <cstdio>
  14. #include <vector>
  15. #include <cmath>
  16. #include <queue>
  17. #include <deque>
  18. #include <stack>
  19. #include <list>
  20. #include <map>
  21. #include <set>
  22.  
  23. #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24. #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25. #define D(x) cout << #x " is " << x << endl
  26.  
  27. const int MAXS = 6 * 50 + 10; // Max number of states in the matching machine.
  28. // Should be equal to the sum of the length of all keywords.
  29.  
  30. const int MAXC = 26; // Number of characters in the alphabet.
  31.  
  32. int out[MAXS]; // Output for each state, as a bitwise mask.
  33. int f[MAXS]; // Failure function
  34. int g[MAXS][MAXC]; // Goto function, or -1 if fail.
  35.  
  36. int buildMatchingMachine(const vector<string> &words, char lowestChar = 'a',
  37.         char highestChar = 'z')
  38. {
  39.     memset(out, 0, sizeof out);
  40.     memset(f, -1, sizeof f);
  41.     memset(g, -1, sizeof g);
  42.     int states = 1; // Initially, we just have the 0 state
  43.     for (int i = 0; i < words.size(); ++i)
  44.     {
  45.         const string &keyword = words[i];
  46.         int currentState = 0;
  47.         for (int j = 0; j < keyword.size(); ++j)
  48.         {
  49.             int c = keyword[j] - lowestChar;
  50.             if (g[currentState][c] == -1)
  51.             { // Allocate a new node
  52.                 g[currentState][c] = states++;
  53.             }
  54.             currentState = g[currentState][c];
  55.         }
  56.         out[currentState] |= (1 << i); // There's a match of keywords[i] at node currentState.
  57.     }
  58.     // State 0 should have an outgoing edge for all characters.
  59.     for (int c = 0; c < MAXC; ++c)
  60.     {
  61.         if (g[0][c] == -1)
  62.         {
  63.             g[0][c] = 0;
  64.         }
  65.     }
  66.  
  67.     // Now, let's build the failure function
  68.     queue<int> q;
  69.     for (int c = 0; c <= highestChar - lowestChar; ++c)
  70.     { // Iterate over every possible input
  71.     // All nodes s of depth 1 have f[s] = 0
  72.         if (g[0][c] != -1 and g[0][c] != 0)
  73.         {
  74.             f[g[0][c]] = 0;
  75.             q.push(g[0][c]);
  76.         }
  77.     }
  78.     while (q.size())
  79.     {
  80.         int state = q.front();
  81.         q.pop();
  82.         for (int c = 0; c <= highestChar - lowestChar; ++c)
  83.         {
  84.             if (g[state][c] != -1)
  85.             {
  86.                 int failure = f[state];
  87.                 while (g[failure][c] == -1)
  88.                 {
  89.                     failure = f[failure];
  90.                 }
  91.                 failure = g[failure][c];
  92.                 f[g[state][c]] = failure;
  93.                 out[g[state][c]] |= out[failure]; // Merge out values
  94.                 q.push(g[state][c]);
  95.             }
  96.         }
  97.     }
  98.  
  99.     return states;
  100. }
  101. int findNextState(int currentState, char nextInput, char lowestChar = 'a')
  102. {
  103.     int answer = currentState;
  104.     int c = nextInput - lowestChar;
  105.     while (g[answer][c] == -1)
  106.         answer = f[answer];
  107.     return g[answer][c];
  108. }
  109.  
  110. int main()
  111. {
  112.     vector<string> keywords;
  113.     keywords.push_back("he");
  114.     keywords.push_back("she");
  115.     keywords.push_back("hers");
  116.     keywords.push_back("his");
  117.     string text = "ahishers";
  118.     buildMatchingMachine(keywords, 'a', 'z');
  119.     int currentState = 0;
  120.     for (int i = 0; i < text.size(); ++i)
  121.     {
  122.         currentState = findNextState(currentState, text[i], 'a');
  123.         if (out[currentState] == 0)
  124.             continue; // Nothing new, let's move on to the next character.
  125.         for (int j = 0; j < keywords.size(); ++j)
  126.         {
  127.             if (out[currentState] & (1 << j))
  128.             { // Matched keywords[j]
  129.                 cout << "Keyword " << keywords[j] << " appears from " << i
  130.                         - keywords[j].size() + 1 << " to " << i << endl;
  131.             }
  132.         }
  133.     }
  134.     return 0;
  135. }

Output:

$ g++ Aho–Corasick.cpp
$ a.out
 
Keyword his appears from 1 to 3
Keyword he appears from 4 to 5
Keyword she appears from 3 to 5
Keyword hers appears from 4 to 7
 
------------------
(program exited with code: 0)
Press return to continue
· Posted by Superadmin on August 10 2022 · 0 Comments · 102 Reads · Print

Comments

No Comments have been Posted.

Post Comment

Please Login to Post a Comment.

Ratings

Rating is available to Members only.

Please login or register to vote.
No Ratings have been Posted.
Render time: 0.77 seconds
10,819,796 unique visits