使用KMP算法实现一个模式匹配.doc

《使用KMP算法实现一个模式匹配.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.课程设计——数据结构设计题目：KMP算法实现一个模式匹配指导老师：徐浩学生姓名：孙文莉班级：信122班..学号：1290842272014年6月16日一、问题描述：使用KMP算法实现一个模式匹配用C/C++编写一个程序实现模式匹配的KMP算法。要求在一个字符串中搜索某个子串，若搜索到就返回子串的位置；若未搜索到，就返回0。首先要输入个主串和模式串，先根据next()函数求模式串的next值，利用KMP算法进行匹配，再用输出函数输出结果！二、设计思路：该算法分为五三个模块：第一模块[input()函数]（利用该函数输入主串和模式串的值）；第二模块[StrLength（

2、）]（利用该函数求各串的长度）；第三模块[get_next()函数]（利用该函数求出模式串的next函数值）；第四模块[Index_KM（）函数]（利用该函数进行主串和模式串之间的匹配）；第五模块[output()函数利用该函数输出匹配结果）。个模块之间的调用关系如下图所示：图4.1是对整个函数的流程图。图4.2是对KMP算法的流程图；图4.3是求next的函数值的流程图。..因水平有限，最终程序清单与这个流程图不同的地方，请谅解。大致思路是一致、、、..三、数据结构定义：#defineMAXSIZE100；intindex_KMP(char*s,char*t,int

3、pos);voidget_next(char*t,int*);用最简单的数组进行KMP模式匹配主串：chars[10]="abcacbabb";模式串：chart[4]="cac";intnext[4];intpos=0;四、系统功能介绍：求模式串的模式值next[]函数用《模式匹配的KMP算法》当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的next函数值。如何求next函数，next函数值仅取决于模式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。由定义知：next[1]=0设next[j]=k，

4、即有：＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1next[j+1]=?　可能有两种情况：一种情况：若tk＝tj则表明在模式串中这就是说next[j+1]=k+1，即next[j＋１]=next[j]+1第二种情况：若tk≠tj则表明在模式串中t1t2…tk＂≠＂tj-k+1tj-k+2…tj＂此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tk≠tj时应将模式向右滑动，使得第next[k]个字符和“主串”中的第j个字符相比较。若next[k]=k′，且tk′＝tj，则说

5、明在主串中第j+1个字符之前存在一个最大长度为k′..的子串，使得＂t1t2…tk′＂=＂tj-k′+1tj-k′+2…tj＂此：next[j+1]=next[k]+1同理若tk′≠tj，则将模式继续向右滑动至使第next[k′]个字符和tj对齐，依此类推，直至tj和模式中的某个字符匹配成功或者不存在任何k′(1

6、0]=next[1]=0;while(i<(int)StrLength(t)){if(j==0

7、

8、t[i]==t[j]){i++;j++;next[i]=j;}elsej=next[j];}}模式匹配KMP算法的实现KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk对准si继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：＂t1t2…tk-1＂=＂s

9、i-k+1si-k+2…si-1＂(4.1)式左边是tk前面的k-1个字符，右边是si前面的k-1个字符。而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：＂t1t2…tj-1＂=＂si-j+1si-j+2…　si-1＂（4.2）因为k