#include <stdio.h>
#include <string.h>
void get_next(char *t,int *next)
{
int i=0,j=-1;
next[0]=-1;
while(t[i]!='\0')
{
if(j==-1 || t[i]==t[j])
{
i++,j++;
printf("%d %d\n",i,j);
if(t[i]!=t[j])
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j];
}
}
int KMP(char *s,char *t,int *next)
{
if(s==NULL || t==NULL)
return -1;
int i=0,j=0;
int len=strlen(t);
while(s[i]!='\0')
{
if(j==-1 || s[i]==t[j])
i++,j++;
else
j=next[j];
if(j==len)
return i-len;
}
return -1;
}
int main(int argc,char **argv)
{
char s[128]="asdfghjkabcabdkhi";
char t[64]="abcabd";
int next[64];
int n=0;
get_next(t,next);
for(n=0;n<6;n++)
printf(" %d",next[n]);
printf("s:%s\n",s);
printf("t:%s\n",t);
printf("%d\n",KMP(s,t,next));
return 0;
}
