本文针对数据结构基础系列网络课程(4)：串中第5课时串的模式匹配（KMP算法）。
问题：串的模式匹配
KMP算法：
#include <stdio.h>#include “sqString.h”void GetNext(SqString t,int next[]) /*由模式串t求出next值*/{int j,k;j=0;k=-1;next[0]=-1;while (j<t.length-1){if (k==-1 || t.data[j]==t.data[k]) /*k为-1或比较的字符相等时*/{j++;k++;next[j]=k;}elsek=next[k];}}int KMPIndex(SqString s,SqString t) /*KMP算法*/{int next[MaxSize],i=0,j=0;GetNext(t,next);while (i<s.length && j<t.length){if (j==-1 || s.data[i]==t.data[j]){i++;j++;/*i,j各增1*/}else j=next[j];/*i不变,j后退*/}if (j>=t.length)(-1);/*返回不匹配标志*/}int main(){SqString s,t;StrAssign(s,”ababcabcacbab”);StrAssign(t,”abcac”);printf(“s:”);DispStr(s);printf(“t:”);DispStr(t);printf(“位置:%d\n”,KMPIndex(s,t));return 0;}
修正后的KMP算法
#include <stdio.h>#include “sqString.h”void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值{int j=0,k=-1;nextval[0]=-1;while (j<t.length){if (k==-1 || t.data[j]==t.data[k]){j++;k++;if (t.data[j]!=t.data[k])nextval[j]=k;elsenextval[j]=nextval[k];}else k=nextval[k];}}int KMPIndex1(SqString s,SqString t) //修正的KMP算法{int nextval[MaxSize],i=0,j=0;GetNextval(t,nextval);while (i<s.length && j<t.length){if (j==-1 || s.data[i]==t.data[j]){i++;j++;}elsej=nextval[j];}if (j>=t.length)return(i-t.length);elsereturn(-1);}int main(){SqString s,t;StrAssign(s,”ababcabcacbab”);StrAssign(t,”abcac”);printf(“s:”);DispStr(s);printf(“t:”);DispStr(t);printf(“位置:%d\n”,KMPIndex1(s,t));return 0;}
，在开始时却总是不厌其烦地渗透入生活的缝隙，
