C++ Program to Perform Finite State Automaton based Search

«
»
This is a C++ Program to search a string using finite automata. Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

Here is source code of the C++ Program to Perform Finite State Automaton based Search. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<string.h>
  3. #define NO_OF_CHARS 256
  4.  
  5. int getNextState(char *pat, int M, int state, int x)
  6. {
  7.     // If the character c is same as next character in pattern,
  8.     // then simply increment state
  9.     if (state < M && x == pat[state])
  10.         return state + 1;
  11.  
  12.     int ns, i; // ns stores the result which is next state
  13.  
  14.     // ns finally contains the longest prefix which is also suffix
  15.     // in "pat[0..state-1]c"
  16.  
  17.     // Start from the largest possible value and stop when you find
  18.     // a prefix which is also suffix
  19.     for (ns = state; ns > 0; ns--)
  20.     {
  21.         if (pat[ns - 1] == x)
  22.         {
  23.             for (i = 0; i < ns - 1; i++)
  24.             {
  25.                 if (pat[i] != pat[state - ns + 1 + i])
  26.                     break;
  27.             }
  28.             if (i == ns - 1)
  29.                 return ns;
  30.         }
  31.     }
  32.  
  33.     return 0;
  34. }
  35.  
  36. /* This function builds the TF table which represents Finite Automata for a
  37.  given pattern  */
  38. void computeTF(char *pat, int M, int TF[][NO_OF_CHARS])
  39. {
  40.     int state, x;
  41.     for (state = 0; state <= M; ++state)
  42.         for (x = 0; x < NO_OF_CHARS; ++x)
  43.             TF[state][x] = getNextState(pat, M, state, x);
  44. }
  45.  
  46. /* Prints all occurrences of pat in txt */
  47. void search(char *pat, char *txt)
  48. {
  49.     int M = strlen(pat);
  50.     int N = strlen(txt);
  51.  
  52.     int TF[M + 1][NO_OF_CHARS];
  53.  
  54.     computeTF(pat, M, TF);
  55.  
  56.     // Process txt over FA.
  57.     int i, state = 0;
  58.     for (i = 0; i < N; i++)
  59.     {
  60.         state = TF[state][txt[i]];
  61.         if (state == M)
  62.         {
  63.             printf("\n pattern found at index %d", i - M + 1);
  64.         }
  65.     }
  66. }
  67.  
  68. // Driver program to test above function
  69. int main()
  70. {
  71.     char *txt = "AABAACAADAABAAABAA";
  72.     char *pat = "AABA";
  73.     search(pat, txt);
  74.     return 0;
  75. }

Output:

advertisement
$ g++ StringMatchingFiniteAutomata.cpp
$ a.out
 
 pattern found at index 0
 pattern found at index 9
 pattern found at index 13
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.