Friday, March 11, 2011

WAP for KMP String Search

e
#include
/* KMP algorithm for string Matching */
main()
{
char *p="This is my first post to this group";
char *T="to this group this is my post";
int len = strlen(p);
int len1 = strlen(T);
printf("len:%d len1:%d\n",len,len1);
int k = 0,i;
int array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
/* Pre processing which takes O(m)*/
for(i = 2; i< len; i++)
{
while(k > 0 && p[k+1] != p[i])
{
k = array[k];
}

if(p[k+1] == p[i])
{
k++;
array[i] = k;
}
}

/* Matching which takes O(n) */
k = 1;
for(i = 0; i< len1; i++)
{

while(k > 0 && p[k+1] != T[i])
{
k = array[k];
}

if(p[k+1] == T[i])
{
k++;
printf("%d %d %c\n",k,i,p[k]);
if(k == 10)
{
printf("String Matched\n");
}
}
}
}

No comments :