模式匹配的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 #include char str[1000],st[1000]; int next[1000]; void getf() {

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;