KMP Algorithm ... A simple and efficient string matching algorithm

// 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;
}