KMP算法求解,当输入定位pos=0时,定位正确,pos=1或其他时,定位就不正确了,希望高手解答,谢谢
程序代码:
#include <stdio.h> #include <string.h> void get_next(char t[],int *next); int index_KMP(char s[],char t[],int *next ,int pos); int main () { char s[]="abcabcaaabcacacc"; char t[]="abcac"; int next[100]={0}; int pos; //pos用来输入s字符串开始定位的位置 int k=0; printf("please input the start position:pos\n"); scanf("%d",&pos); get_next(t,next); for(int i=0;i<10;i++) printf("%d",next[i]); k=index_KMP(s,t,next,pos); if(k!=0) printf("the first position is%d\n",k); else printf("can not find"); return 0; } int index_KMP(char s[],char t[],int *next ,int pos)//利用KMP算法定位 { int i=pos; int j=0; while(i<strlen(s) && j<strlen(t)) { if(j==-1||s[i]==t[j]) { ++i; ++j; } else { j=next[j]; } } if(j>=strlen(t)) return i-strlen(t)+1; else return 0; } void get_next(char t[],int *next)//获取next数组中的数值 { int i=0; int j=-1; next[0]=-1; while(i<strlen(t)) { if(j==-1||t[i]==t[j]) { ++i; ++j; next[i]=j; } else { j=next[j]; } } }