欢迎来到天天文库
浏览记录
ID:48210052
大小:182.00 KB
页数:8页
时间:2020-01-22
《使用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+1]=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′(16、0]=next[1]=0;while(i<(int)StrLength(t)){if(j==07、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"="s9、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
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
此文档下载收益归作者所有