文档介绍：模式匹配的KMP算法
学生姓名：侯成龙 指导老师：罗心
摘要本课程设计主要解决用模式匹配的KMP算法进行字串定位的程序设计。在本课 程设计中，系统开发平台为Windows XP,程序设计设计语言采用Visual C++,程序运 行串。
2设计思路与方案
注意到模式匹配的KMP算法是对模式匹配简单算法改进后的算法，所以有必要先介 绍简单模式匹配算法及其基本思想，进而提出一种改进后的模式匹配算法---KMP算法。因 为KMP算法是在已知模式串的next函数值的基础上执行的，所以又要先实现求模式串next 函数值的算法。
在本课程设计中，运用串的模式匹配的KMP算法进行子串的定位操作，要实现这一过 程主要用到以下函数：
求next函数值的算法：
void GetNext(char T[MAXSTRLEN],int (&next)[64])
计算next函数修正值的算法：
void GetNextVal(char T[MAXSTRLEN],int (&next)[64])
KMP算法：
int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64],int pos) 主函数：
void main()
3详细实现
采用定长顺序存储结构，可以写出不依赖于其他串操作的基本匹配算法。该算法的基 本思想是：从主串
S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个 比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至 模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为 和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为零。 算法如下：
int Index(SString S,SString T,int pos) {
〃返回子串T在主串S中的第pos个字符之后的位置的。若不存在，则函数值为0。
〃其中，T 非空，1忍pos 忍 StrLength(S)。
int i=pos; int j=1;
while (i<=S[0]&&j<=T[0]) {
if (S[i]==T[j]) {++i;++j;}
else {i=i-j+2; j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}// Index
——KMP算法
, 算法。此算法可以在O(n+m)的时间内数量级上完成串的模式匹配操作。其改进之处在于： 每当一趟匹配过程中出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部 分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较°KMP算法如 下：
int Index_KMP(SString S,SString T,int (&nextval)[64],int pos) {
〃利用模式串T的next函数T求T在主串S中的第pos个字符之后的位置的
// KMP 算法。其中，T 非空，1忍pos忍StrLength(S)。
int i=pos; int j=1;
while (i<=S[0]&&j<=T[0]) {
if (j=0||S[i]=T[j]) {++i;++j;}
else j=nextval[j];
}
if(j>T[0]) return i-T[0];
else return 0;
}// Index_KMP
模式串的next函数的定义：
<0 , 当[二1时
nest [ j ]= Max {k | j且 pi. . . pLri = pj-ld-i. . . pj-i
L ， 其他情况
例如：P=〃abaabcac" 则
1
2
3
4
5
6
7
8
neKt [j]:
0
1
1
2
2
3
1
2 [7]
KMP算法是在已知模式串的next函数值的基础上执行的，求next函数值的算法如下 所示：
void get_next(SString T, int next [ ]) {
〃求模式串T的next函数值并存入数组next。
i=1; next [1]=0; j=0;
while(i<T[0]) {
if (j=0||T[i]=T[j]) {
++i; ++j;
next [i]=j;}
else j=n