jmu-ds-实现KMP

 jmu-ds-实现KMP

#include <stdio.h>
#include<string.h>
const int MAX_LEN=20010;
void get_next(char str[],int len,int next[])
{
int i=0,j=0;
next[0]=-1;
for(i=1;i<len;i++){
while(j>0&&str[i]!=str[j])
j=next[j-1];
if(str[i]==str[j] )j++;
next[i]=j;
}
}
int find_pattern(char s[],int len_s,char t[],int len_t,int next[])
{
int i=0,j=0;
while(i<len_s&&j<len_t){
if(
j==-1||s[i]==t[j]
){
j++;i++;
}else{
j=next[j];
}
}
if(j==len_t)
return i-j;
else
return -1;
}
int main (){
int cas,a;
char s[MAX_LEN],t[MAX_LEN];
int next[MAX_LEN];
scanf("%d",&cas);
while(cas--){
scanf("%s %s",s,t);
int len_s=strlen(s);
int len_t=strlen(t);
get_next(t,len_t,next);
a=find_pattern(s,len_s,t,len_t,next);
if(a==-1)
printf("not find!\n");
else
printf("%d\n",a);
}
return 0;
}