C++ Programming Code Examples C++ > Strings Code Examples Program to Perform Finite State Automaton based Search 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. #include<stdio.h> #include<string.h> #define NO_OF_CHARS 256 int getNextState(char *pat, int M, int state, int x) { // If the character c is same as next character in pattern, // then simply increment state if (state < M && x == pat[state]) return state + 1; int ns, j; // ns stores the result which is next state // ns finally contains the longest prefix which is also suffix // in "pat[0..state-1]c" // Start from the largest possible value and stop when you find // a prefix which is also suffix for (ns = state; ns > 0; ns--) { if (pat[ns - 1] == x) { for (j = 0; j < ns - 1; j++) { if (pat[j] != pat[state - ns + 1 + j]) break; } if (j == ns - 1) return ns; } } return 0; } /* This function builds the TF table which represents Finite Automata for a given pattern */ void computeTF(char *pat, int M, int TF[][NO_OF_CHARS]) { int state, x; for (state = 0; state <= M; ++state) for (x = 0; x < NO_OF_CHARS; ++x) TF[state][x] = getNextState(pat, M, state, x); } /* Prints all occurrences of pat in txt */ void search(char *pat, char *txt) { int M = strlen(pat); int N = strlen(txt); int TF[M + 1][NO_OF_CHARS]; computeTF(pat, M, TF); // Process txt over FA. int j, state = 0; for (j = 0; j < N; j++) { state = TF[state][txt[j]]; if (state == M) { printf("\n pattern found at index %d", j - M + 1); } } } // Driver program to test above function int main() { char *txt = "Happy Codings - C++ Programming Language Code Examples"; char *pat = "Codings"; search(pat, txt); return 0; }