// KMP algorithm is a string matching algorithm,It takes O(n) complexity to search a substring out of a text.
It creates a suffix table to make it fast so overall complexity becomes O(n+m) where m is the length of the substring whereas n is length of the text, space complexity is O(n) to create the suffix table for the text.
For more concept Click here
Note:- This program also print the resultant of the suffix table...
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int *PrefixTable(char P[])
{
int m=strlen(P);
int *F;
F=malloc(sizeof(int)*m);
int i=0;
while(i<m)
{
F[i]=0;
i++;
}
int j=0;i=1;
while(i<=m)
{
if(P[i]==P[j])
{
F[i]=j+1;
i++,j++;
}
else if(j>0)
j=F[j-1];
else
i++;
}
return F;
}
int KMP(char str[],int n,char P[],int m,int *F)
{int i=0,j=0,flag=0;
while(i<n)
{
if(str[i]==P[j])
{
if(j==m-1)
{
printf("\nString Found at position %d",i-j);;
j=0;
flag=1;
i++;
}
else
{
i++;
j++;
}
}
else if(j>0)
j=F[j-1];
else
i++;
}
return flag;
}
int main(void)
{
char P[1000];
char str[1000];int m;
printf("Enter the large string\n");
scanf("%[^\n]%*c",&str);
printf("\nEnter the string for which you are searching for\n");
scanf("%[^\n]%*c",&P);
m=strlen(P);
int *F=PrefixTable(P);
int i=0;
printf("Prefix Table is \n\n");
while(P[i]!='\0')
{
printf("%d ",F[i++]);
}
int n=strlen(str);
int k=KMP(str,n,P,m,F);
if(k==0)
printf("No such string found");
return 0;
}
It creates a suffix table to make it fast so overall complexity becomes O(n+m) where m is the length of the substring whereas n is length of the text, space complexity is O(n) to create the suffix table for the text.
For more concept Click here
Note:- This program also print the resultant of the suffix table...
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int *PrefixTable(char P[])
{
int m=strlen(P);
int *F;
F=malloc(sizeof(int)*m);
int i=0;
while(i<m)
{
F[i]=0;
i++;
}
int j=0;i=1;
while(i<=m)
{
if(P[i]==P[j])
{
F[i]=j+1;
i++,j++;
}
else if(j>0)
j=F[j-1];
else
i++;
}
return F;
}
int KMP(char str[],int n,char P[],int m,int *F)
{int i=0,j=0,flag=0;
while(i<n)
{
if(str[i]==P[j])
{
if(j==m-1)
{
printf("\nString Found at position %d",i-j);;
j=0;
flag=1;
i++;
}
else
{
i++;
j++;
}
}
else if(j>0)
j=F[j-1];
else
i++;
}
return flag;
}
int main(void)
{
char P[1000];
char str[1000];int m;
printf("Enter the large string\n");
scanf("%[^\n]%*c",&str);
printf("\nEnter the string for which you are searching for\n");
scanf("%[^\n]%*c",&P);
m=strlen(P);
int *F=PrefixTable(P);
int i=0;
printf("Prefix Table is \n\n");
while(P[i]!='\0')
{
printf("%d ",F[i++]);
}
int n=strlen(str);
int k=KMP(str,n,P,m,F);
if(k==0)
printf("No such string found");
return 0;
}
No comments:
Post a Comment