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

Output:

$ gcc FiniteStateAutomatonBasedSearch.c
$ ./a.out
 
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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.