数据结构例程——串的模式匹配（KMP算法）

本文针对数据结构基础系列网络课程(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; } else k=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) return(i-t.length); /*返回匹配模式串的首字符下标*/ else return(-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; else nextval[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++; } else j=nextval[j]; } if (j>=t.length) return(i-t.length); else return(-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; } 相关资源：串的模式匹配问题