Showing posts with label Finite Automata. Show all posts
Showing posts with label Finite Automata. Show all posts

Sunday 17 July 2016

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