Program 4: Finite Automata string matching

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve String matching problem using Finite Automata and determine its performance.

#include<stdio.h>

#include<string.h>

#define CHARS 256

int getNextState(char pat[30], int M, int state, int x)

{

            int ns, i;

            if (state < M && x == pat[state])

                        return state+1;

            for (ns = state; ns > 0; ns--)

            {

                        if(pat[ns-1] == x)

                        {

                                    for(i = 0; i < ns-1; i++)

                                    {

                                                if (pat[i] != pat[state-ns+1+i])

                                                break;

                                    }

                                    if (i == ns-1)

                                                return ns;

                        }

            }

            return 0;

}

void computeTF(char pat[30], int M, int TF[][CHARS])

{

            int state, x;

            for (state = 0; state <= M; ++state)

                        for (x = 0; x < CHARS; ++x)

                                    TF[state][x] = getNextState(pat, M,  state, x);

}

void search(char pat[30], char txt[30])

{

            int M = strlen(pat);

            int N = strlen(txt);

            int TF[M+1][CHARS];

            int i, state=0;

            computeTF(pat, M, TF);

           for (i = 0; i < N; i++)

            {

                        state = TF[state][txt[i]];

                        if (state == M)

                        {

                                    printf ("\nPattern found at index %d", i-M+1);

                        }

            }

}

int main()

{

            char txt[30], pat[30];

            printf("\nEnter the text:");

            gets(txt);

            printf("\nEnter the pattern:");

            gets(pat);

            search(pat, txt);

            return 0;

}

Output:

Case 1:

Enter the text: ababacabaabcaba

Enter the pattern: aba

Pattern found at index 0

Pattern found at index 2

Pattern found at index 6

Pattern found at index 12

Case 2:

Enter the text: abababacaba

Enter the pattern: ababaca

Pattern found at index 2