《使用KMP算法实现一个模式匹配》由会员分享，可在线阅读，更多相关《使用KMP算法实现一个模式匹配（8页珍藏版）》请在装配图网上搜索。
1、课程设计数据结构KMP算法实现一个模式匹配 指导老师：徐浩 学生姓名：孙文莉 班级 ：信122班学号:1290842272014年6月16日一、问题描述：使用KMP算法实现一个模式匹配用C/C+编写一个程序实现模式匹配的KMP算法。要求在一个字符串中搜 索某个子串，若搜索到就返回子串的位置；若未搜索到，就返回0。首先要输 入个主串和模式串，先根据next（）函数求模式串的next值，利用KMP算法进 行匹配，再用输出函数输出结果！二、设计思路：该算法分为五三个模块：第一模块inpu t（）函数（利用该函数输入主串和模式串的值）；第二模块StrLength（）（利用该函数求各串的长度）；第三模块
2、get_next（）函数（利用该函数求出模式串的next函数值）；第四模块Index_KM（）函数（利用该函数进行主串和模式串之间的匹配）; 第五模块output（）函数利用该函数输出匹配结果）。个模块之间的调用关系如下图所示：图4.1是对整个函数的流程图。图4.2 是对KMP算法的流程图；图4.3是求next的函数值的流程图。因水平有限，最终程序清单与这个流程图不同的地方，请谅解。大致思路是一致、三、数据结构定义：#defi ne MAXSIZE 100；int in dex_KMP(char *s,char *t, int pos);void get_ next(char *t,i nt
3、*);用最简单的数组进行KMP模式匹配主串：char s10=”abcacbabb”；模式串：char t4=”cac”；int next4;int pos=0;四、系统功能介绍：求模式串的模式值next 函数用模式匹配的KMP算法当主串和模式串匹配不相等是，模式串应向右移 动一段距离，此时我们需要得到模式串的next函数值。如何求next函数，next函数值仅取决于模式本身而和主串无关。我们可以 从分析next函数的定义出发用递推的方法求得next函数值。由定义知：nex tl=0 设 nex tj二k,即有：tl t2 tk-1 二t j-k+It j-k+2 tj-1 nextj+1=?
4、可能有两种情况：一种情况：若tk =tj则表明在模式串中这就 是说 nextj+1=k+1，即 nextj+l=nextj+1 第二种情况：若 tk Htj 则 表明在模式串中tl t2tk H tj-k+1 tj-k+2tj 此时可把求next 函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前 在匹配的过程中，已有(4.6)式成立，则当tk Htj时应将模式向右滑动，使得 第nextk个字符和“主串”中的第j个字符相比较。若nextk二k，且t k二tj,则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得 tl t2 t k二tj-k +1 t j- kz
5、 +2 tj 此：nex tj+l=nex tk+l同理若t k，Htj,则将模式继续向右滑动至使第nextk 个字符和tj 对齐，依此类推，直至tj和模式中的某个字符匹配成功或者不存在任何k，(1 k，kj)满足，此时若tlHtj+1 ,则有：nextj+1 = 1否则若t1=tj+1 , 则有：nextj+1=0综上所述，求next函数值过程的算法如下：void get_ next(char *t,i nt *n ext) int i=1,j=0;n ext0 =n ext1=0;while (i(i nt)StrLe ngth(t)if (j=0|ti=tj)i+；j+；n exti=j
6、;else j=n extj;模式匹配KMP算法的实现KMP算法的思想：主串s,模式t希望某趟在si和tj匹配失败后，指针i不回溯, 模式t向右“滑动”至某个位置上，使得tk对准s i继续向右进行。显然，现 在问题的关键是串t “滑动”到哪个位置上？不妨设位置为k,即si和tj匹配失 败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要 满足这一假设，就要有如下关系成立：t1 t2tk-1 = si-k+1 si-k+2 si-1 (4.1)式左边是tk前面的k-1个字符，右边是si前面的k-1个字符。而 本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：t1 t
7、2tj-1 =si-j+1 si-j+2 si-1 (4.2)因为 kvj,所以有：tj-k+1 tj-k+2 tj-1 =si-k+1 si-k+2 si-1 (4.3)式左边是tj前面的k-1个字符，右边是si前 面的k-1个字符，通过(4.1)和(4.3)得到关系：t1 t2tk-1 = tj-k+1 tj-k+2tj-1 (4.4)结论：某趟在si和tj匹配失败后，如果模式串中有满足 关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字 符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即 可。在求得模式的next函数之后，匹配可如下进行
8、：假设以指针i和j分别指示主串 和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中siHtj, 则i和j分别增1,若siHtj匹配失败后，则i不变，j退到nextj位置再比较， 若相等，则指针各自增1,否则j再退到下一个next值的位置，依此类推。直 至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1 继续进行匹配；另一种是j退到值为零(即模式的第一个字符失配)，则此时i 和j也要分别增1,表明从主串的下一个字符起和模式重新开始匹配。KMP算法如下：int In dex_KMP(char *s,char *t,i nt pos)int i=pos,j=
9、1;while (in)return i-n+1;elsereturn 0;五、程序清单：#in elude vstdio.h#i nclude vstri ng.h#defi ne MAXSIZE 100int in dex_KMP(char *s,char *t, int pos); void get_ next(char *t,i nt *);char s10=”abcacbabb”；char t4=cac;int next4;int pos=0;int mai n()printf (主串是：n,s);printf(”模式串是：n,t);int n;get_ next(t, next);
10、 n=in dex_KMP(s,t,pos); prin tf(%d, n);return 0; int in dex_KMP(char *s,char *t, int pos)int i=pos,j=1;while (i(i nt)strle n(t) return i-strle n(t)+1;elsereturn 0;void get_ next(char *t,i nt *n ext)int i=1,j=0;n ext0 =n ext1=0; while (iv(i nt)strle n(t)if (j=0|ti=tj) i+; j+;n exti=j;else j=n extj;运行与调试分析等不知道什么原因，明明运行成功了，就是显示不出来，水平有限(_)
使用KMP算法实现一个模式匹配
