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

. . . . 课 程 设 计 数据结构 设计题目：KMP算法实现一个模式匹配 指导老师：徐浩 学生姓名： 孙文莉 班级 ： 信122班 学号 ：129084227 2014年6月16日1、 问题描述：使用KMP算法实现一个模式匹配 用C/C+编写一个程序实现模式匹配的KMP算法。要求在一个字符串中搜索某个子串，若搜索到就返回子串的位置；若未搜索到，就返回0。 首先要输入个主串和模式串，先根据next( )函数求模式串的next值，利用KMP 算法进行匹配，再用输出函数输出结果！ 2、 设计思路：该算法分为五三个模块：第一模块input( )函数（利用该函数输入主串和模式串的值）；第二模块StrLength（）（利用该函数求各串的长度）；第三模块get_next( )函数（利用该函数求出模式串的next函数值）；第四模块Index_KM（）函数（利用该函数进行主串和模式串之间的匹配）； 第五模块output( )函数利用该函数输出匹配结果）。个模块之间的调用关系如下图所示：图4.1是对整个函数的流程图。图4.2是对KMP算法的流程图；图4.3是求next的函数值的流程图。 因水平有限，最终程序清单与这个流程图不同的地方，请谅解。大致思路是一致、3、 数据结构定义：#define MAXSIZE 100；int index_KMP(char *s,char *t,int pos); void get_next(char *t,int *); 用最简单的数组进行KMP模式匹配主串：char s10=abcacbabb; 模式串：char t4=cac; int next4; int pos=0; 4、 系统功能介绍： 求模式串的模式值next函数用模式匹配的KMP算法当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的next函数值。 如何求next函数，next函数值仅取决于模式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。由定义知：next1=0设nextj=k，即有：t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 nextj+1=?可能有两种情况：一种情况：若tk tj 则表明在模式串中这就是说nextj+1=k+1，即nextj=nextj+1 第二种情况：若tk tj 则表明在模式串中t1 t2 tk tj-k+1 tj-k+2 tj 此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tk tj 时应将模式向右滑动，使得第nextk个字符和“主串”中的第j个字符相比较。若nextk=k，且t ktj，则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得t1 t2 t k =tj-k+1 tj- k+2 tj 此： nextj+1=nextk+1 同理若t k tj，则将模式继续向右滑动至使第nextk个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k(1 kk j)满足，此时若t1tj+1 ， 则有：nextj+1=1 否则若t1=tj+1 ，则有：nextj+1=0 综上所述，求next函数值过程的算法如下： void get_next(char *t,int *next) int i=1,j=0; next0=next1=0; while (i(int)StrLength(t) if (j=0|ti=tj) i+; j+; nexti=j; else j=nextj; 模式匹配KMP算法的实现KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk 对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：t1 t2 tk-1 =si-k+1 si-k+2 si-1 (4.1)式左边是tk前面的k-1个字符，右边是si 前面的k-1个字符。而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：t1 t2 tj-1 =si-j+1 si-j+2 si-1 （4.2）因为kj，所以有：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 t2 tk-1 =tj-k+1 tj-k+2 tj-1 (4.4)结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中sitj，则i和j分别增，若sitj 匹配失败后，则i不变，j退到nextj位置再比较，若相等，则指针各自增，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增继续进行匹配; 另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增，表明从主串的下一个字符起和模式重新开始匹配。KMP算法如下：int Index_KMP(char *s,char *t,int pos) int i=pos,j=1; while (i=m&jn) return i-n+1; else return 0; 5、 程序清单：#include #include #define MAXSIZE 100int index_KMP(char *s,char *t,int pos); void get_next(char *t,int *); char s10=abcacbabb; char t4=cac; int next4; int pos=0; int main() printf (主串是：n,s); printf(模式串是：n,t); int n; get_next(t,next); n=index_KMP(s,t,pos); printf(%d,n); return 0; int index_KMP(char *s,char *t,int pos) int i=pos,j=1; while (i=(int)strlen(s)&j(int)strlen(t) return i-strlen(t)+1; else return 0; void get_next(char *t,int *next) int i=1,j=0; next0=next1=0; while (i_) 欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力。赠语； 1、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就