String Matching with Finite Automata
👉How it works?????
♦Each character in pattern has a state.
♦Each match sends the automaton into a new state
♦If all the characters in the pattern has been
matched, the automaton enters the accepting state.
♦Otherwise, the automaton will return to a suitable
state according to the current state and the input character such that this returned state reflects the
maximum advantage we can take from the previous
👉 Preprocessing of pattern
lets try example....
pattern= "ababc"
lets make state transition table
1)Get the alphabet of pattern
alphabet of pattern ={a,b,c}
2)Get the length of the pattern=5
lets draw the table.
1)
2)
consider pattern
lets fill "s0" column
a → a its match so value = 1
a → b its doesn't match so value = 0
a → c its match so value = 0
lets fill "S1" column
ab → aa its match
ab aa
↖ ↗
value=1
ab → ab its match
value =2
ab → ac its doesn't match
value =0
lets fill "S2" column
aba → aba its match
value =3
aba → abb its doesn't match
value =0
aba → abc its match
value =0
lets fill "S3" column
abab → abaa its match
value =1
abab → abab its match
value =4
abab → abac its doesn't match
value =0
finally.....
👉C code for Finite Automata
#include <stdio.h>
#include<string.h>
// the size of the alphabet
#define alphabet 256
void table(char pattern[], int tb[][alphabet])
{
int m = strlen(pattern),i,level,x;
for(level=0;level<=m;level++)
{
for(x=0;x<alphabet;x++)
{
tb[level][x]=calculate(pattern,level,x);
}
}
}
int calculate(char pattern[],int level, int x)
{
int m =strlen(pattern),i;
if(level<m && x==pattern[level])
return level+1;
for(int n =level;n>0;n--)
{
if (pattern[n-1]== x)
{
for( i=0;i<n-1;i++)
{
if(pattern[i]!=pattern[level-n+i+1])
break;
}
if(i==n-1)
{
return n;
}
}
}
return 0;
}
void search(char pattern[], char text[])
{
int m =strlen(pattern);
int t =strlen(text);
int tb[m+1][alphabet];
table(pattern,tb);
int i,level=0,match=0;
for(i=0;i<t;i++)
{
level = tb[level][text[i]];
if(level == m)
{
printf("there is a string match %d ",i-m+1);
match =1;
}
}
if (match==0)
{
printf("there is no match");
}
}
int main()
{
search("hi","lahiruhi");
}
👉 Time complexity
☺matching time complexity=O(n)
☺processing complexity =O(mà©©)
n=length of text
m=length of pattern
à©©= alphabet size
Thank You..............
Good job
ReplyDelete