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
