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

-.z.课程设计——数据构造设计题目：KMP算法实现一个模式匹配指导教师：徐浩学生：文莉班级：信122班**：1290842272021年6月16日问题描述：使用KMP算法实现一个模式匹配用C/C++编写一个程序实现模式匹配的KMP算法。要求在一个字符串中搜索*个子串，假设搜索到就返回子串的位置；假设未搜索到，就返回0。首先要输入个主串和模式串，先根据ne*t()函数求模式串的ne*t值，利用KMP算法进展匹配，再用输出函数输出结果！设计思路：该算法分为五三个模块：第一模块[input()函数]〔利用该函数输入主串和模式串的值〕；第二模块[StrLength〔〕]〔利用该函数求各串的长度〕；第三模块[get_ne*t()函数]〔利用该函数求出模式串的ne*t函数值〕；第四模块[Inde*_KM〔〕函数]〔利用该函数进展主串和模式串之间的匹配〕；第五模块[output()函数利用该函数输出匹配结果〕。个模块之间的调用关系如以下图所示：图4.1是对整个函数的流程图。图4.2是对KMP算法的流程图；图4.3是求ne*t的函数值的流程图。因水平有限，最终程序清单与这个流程图不同的地方，请谅解。大致思路是一致、、、数据构造定义：*defineMA*SIZE100；intinde*_KMP(char*s,char*t,intpos);voidget_ne*t(char*t,int*);用最简单的数组进展KMP模式匹配主串：chars[10]="abcacbabb";模式串：chart[4]="cac";intne*t[4];intpos=0;系统功能介绍：求模式串的模式值ne*t[]函数用"模式匹配的KMP算法"当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的ne*t函数值。如何求ne*t函数，ne*t函数值仅取决于模式本身而和主串无关。我们可以从分析ne*t函数的定义出发用递推的方法求得ne*t函数值。由定义知：ne*t[1]=0设ne*t[j]=k，即有：＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1ne*t[j+1]="可能有两种情况：一种情况：假设tk＝tj则说明在模式串中这就是说ne*t[j+1]=k+1，即ne*t[j＋１]=ne*t[j]+1第二种情况：假设tk≠tj则说明在模式串中t1t2…tk＂≠＂tj-k+1tj-k+2…tj＂此时可把求ne*t函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tk≠tj时应将模式向右滑动，使得第ne*t[k]个字符和“主串〞中的第j个字符相比拟。假设ne*t[k]=k′，且tk′＝tj，则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串，使得＂t1t2…tk′＂=＂tj-k′+1tj-k′+2…tj＂此：ne*t[j+1]=ne*t[k]+1同理假设tk′≠tj，则将模式继续向右滑动至使第ne*t[k′]个字符和tj对齐，依此类推，直至tj和模式中的*个字符匹配成功或者不存在任何k′(1<k′<k<…<j)满足，此时假设t1≠tj+1，则有：ne*t[j+1]=1否则假设t1=tj+1，则有：ne*t[j+1]=0综上所述，求ne*t函数值过程的算法如下：voidget_ne*t(char*t,int*ne*t){inti=1,j=0;ne*t[0]=ne*t[1]=0;while(i<(int)StrLength(t)){if(j==0||t[i]==t[j]){i++;j++;ne*t[i]=j;}elsej=ne*t[j];}}模式匹配KMP算法的实现KMP算法的思想：主串s，模式t希望*趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动〞至*个位置上，使得tk对准si继续向右进展。显然，现在问题的关键是串t“滑动〞到哪个位置上.不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动〞，使tk和si对准继续向右进展比拟，要满足这一假设，就要有如下关系成立：＂t1t2…tk-1＂=＂si-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<j，所以有：＂tj-k+1tj-k+2…tj-1＂=＂si-k+1si-k+2…si-1＂(4.3)式左边是tj前面的k-1个字符，右边是si前面的k-1个字符，通过(4.1)和(4.3)得到关系：＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1＂(4.4)结论：*趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动〞至使tk和si对准，继续向右进展比拟即可。在求得模式的ne*t函数之后，匹配可如下进展：假设以指针i和j分别指示主串和模式中的比拟字符，令i的初值为pos，j的初值为1。假设在匹配过程中si≠tj，则i和j分别增１，假设si≠tj匹配失败后，则i不变，j退到ne*t[j]位置再比拟，假设相等，则指针各自增１，否则j再退到下一个ne*t值的位置，依此类推。直至以下两种情况：一种是j退到*个ne*t值时字符比拟相等，则i和j分别增１继续进展匹配;另一种是j退到值为零〔即模式的第一个字符失配〕，则此时i和j也要分别增１，说明从主串的下一个字符起和模式重新开场匹配。KMP算法如下：intInde*_KMP(char*s,char*t,intpos){inti=pos,j=1;while(i<=m&&j<=n){if(j==0||s[i]==t[j-1]){i++;j++;}elsej=ne*t[j];}if(j>n)returni-n+1;elsereturn0;}程序清单：*include<stdio.h>*include<string.h>*defineMA*SIZE100intinde*_KMP(char*s,char*t,intpos);voidget_ne*t(char*t,int*);chars[10]="abcacbabb";chart[4]="cac";intne*t[4];intpos=0;intmain(){printf("主串是：\n",s);printf("模式串是：\n",t);intn;get_ne*t(t,ne*t);n=inde*_KMP(s,t,pos);printf("%d",n);return0;}intinde*_KMP(char*s,char*t,intpos){inti=pos,j=1;while(i<=(int)strlen(s)&&j<=(int)strlen(t)){if(j==0||s[i]==t[j-1]){i++;j++;}elsej=ne*t[j];}if(j>(int)strlen(t))returni-strlen(t)+1;elsereturn0;}voidget_ne*t(char*t,int*ne*t){inti=1,j=0;ne*t[0]=ne*t[1]=0;while(i<(int)strlen(t)){