课程设计——数据结构 设计题目： KMP 算法实现一个模式匹配 指导老师：徐浩 学生： 文莉 班级 ： 信 122 班 学号 ： 129084227 2024 年 6 月 16 日一、问题描述：使用 KMP 算法实现一个模式匹配用 C/C++编写一个程序实现模式匹配的 KMP 算法。要求在一个字符串中搜索某个子串，若搜索到就返回子串的位置；若未搜索到，就返回 0。 首先要输入个主串和模式串，先根据 next( )函数求模式串的 next 值，利用 KMP 算法进行匹配，再用输出函数输出结果！二、设计思路：该算法分为五三个模块：第一模块[input( )函数]（利用该函数输入主串和模式串的值）；第二模块[StrLength（）]（利用该函数求各串的长度）；第三模块[get_next( )函数]（利用该函数求出模式串的 next 函数值）；第四模块[Index_KM（）函数]（利用该函数进行主串和模式串之间的匹配）； 第五模块[output( )函数利用该函数输出匹配结果）。个模块之间的调用关系如下图所示：图 4.1 是对整个函数的流程图。图4.2 是对 KMP 算法的流程图；图 4.3 是求 next 的函数值的流程图。开始结束用intput( )输入串输出长度m,nnext( )函数值StrLength( )get_next( )i++; j++;next[i-1]=j;i=lti-lt+10输出匹配结果调用output ( )YNNYYNYNY因水平有限，最终程序清单与这个流程图不同的地方，请谅解。大致思路是一致、、、三、数据结构定义：#define MAXSIZE 100；int index_KMP(char *s,char *t,int pos); void get_next(char *t,int *); 用最简单的数组进行 KMP 模式匹配主串：char s[10]="abcacbabb"; 模式串：char t[4]="cac"; int next[4]; int pos=0; 四、系统功能介绍：求模式串的模式值 next[]函数用《模式匹配的 KMP 算法》当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的 next 函数值。 如何求 next 函数，next 函数值仅取决于模式本身而和主串无关。我们可以从分析 next 函数的定义出发用递推的方法求得 next 函数值。由定义知：next[1]=0 设 next[j]=k，即有：＂t1 t2 … tk-1 ＂ =＂tj-k+1 tj-k+2 … tj-1 next[j+1]=? 可能有两种情况：一种情况：若 tk ＝tj 则表明在模式串中这就是说...
