发布时间 : 星期五 文章模式匹配的kmp算法更新完毕开始阅读
接着进行第三轮比较。模式串P中的第7个字符发生失配,此时j=6。 可知下一轮匹配的起始比较位置为P f(6-1)+1,即p2。目标指针不发生回溯,仍指向失配位置。接着进行第四轮匹配,第四轮匹配成功。
T c t c a a t c a c a a t c a t P c a a t c a t (成功) #include
int j=0,k=-1,m; next[0]=-1; m=strlen(st); while(j if(k==-1||st[j]==st[k]) { j++;k++; if(st[j]!=st[k]) next[j]=k; } } } else next[j]=next[k]; else k=next[k]; for(j=0;j int KMP() { int i=0,j=0; memset(next,0,sizeof(next)); getf(); int m=strlen(str); int n=strlen(st); while(i if(j==-1||str[i]==st[j]) { } else j=next[j]; i++;j++; } if(j>=n) return (i-n); else return -1; int main() { } gets(str); gets(st); int k=KMP(); printf(\return 0;