基于改进kmp算法的字符文件子串查找

1 / 8 数据结构实验报告 学号：2015111898 姓名：许明华 专业：计算机科学与技术 知识范畴：字符串 完成日期：2017 年 4 月 14 日 实验题目：基于改进 KMP 算法的字符文件子串查找 实验内容及要求： 从键盘输入字符文件名以及子串，用改进 KMP 算法在字符文件中实现子串查找。要求程 序输出子串的改进 nextval 数组元素值以及子串在文件中成功匹配的次数（查找失败输出成 功匹配次数为 0） 。 实验目的：掌握子串查找的 KMP 算法。 数据结构设计简要描述： 序言： 这是本学期第四个实验，本实验是要求我们将一个文件中的字符串读取出来，并自己从 键盘上输入一个字符串来进行匹配，并用 kmp 算法来进行字符串的匹配查找； 数据结构简单设计：数据结构简单设计： 本实验主要可分为三大模块，第一，从文件中读取出主串，并将其保存在一个字符数组 中；第二，通过我们从键盘上输入的字符串来获得改进的 nextval 数组，而在改进的 nextval 数组求值算法中，变量还是跟踪的是 next 数组的值；第三，利用 kmp 算法来进行主 串（char *s）和模式子串（char *t）的匹配，并求出成功匹配的次数； 算法设计简要描述： 1,求 nextval 数组的值，我们将不需要用到 next 数组就可以直接求出 nextval 数组的值， 使 nextval 得出示值为-1，即 nextval0 = k = -1;将子串下标 j 初始化为 1，然后通过 tj和 tk的值变化来获得 nextval 数组的值，其中的要点是，k 值跟踪的仍然是未改进的 nextj的值； 2，利用 kmp 算法来进行主串和模式子串的匹配，定义一个记录匹配的变量 c = 0，主串 下标为 i= 0，子串下标 j = 0，当主串和子串第一个元素匹配成功后，进行 i+和 j+操作， 都遍历到下一个元素；当进行一次成功匹配时，将子串的下标回溯到初始位置，记录变量 c+，此时主串下标已经到达匹配成功的下一个元素，再继续进行匹配，知道主串到达末尾， 评分 满分5 分 2 / 8 结束匹配。 输入/输出设计简要描述： 1，输入：输入存储主串的文件名，输入子串； 2，输出：当输入文件名后，会打印输出主串；当输入子串后，会打印输出 nextval 数组 的值以及匹配成功的次数值 c。 编程语言说明： 1，编程软件，Code Blocks 16.0； 2，代码均用 C 语言实现； 3，输入输出采用 C 语言的 printf 和 scanf 函数； 4，程序注释采用 C/C+规范； 主要函数说明： void write(char);/读取主串函数 void get_nextval(char ,int);/获得 nextval 数组函数 int index_kmp(char ,char , int);/kmp 算法函数 void print_nextval(int , int);/输出 nextval 数组函数 程序测试简要报告： 见截图： 1， 3 / 8 2， 源程序代码： #include #include #include int nextval32 = -999;/定义一个 nextval 数组,并进行初始化 /函数声明 void write(char s);/读取主串函数 void get_nextval(char ,int);/获得 nextval 数组函数 int index_kmp(char ,char , int);/kmp 算法函数 void print_nextval(int , int);/输出 nextval 数组函数 /从文件中将主串读出来并保存在 s数组中 void write(char s256) char filename10; 4 / 8 FILE *fp; printf(“请输入文件名：n“); scanf(“%s“,filename); if(fp = fopen(filename,“r“) = NULL) printf(“can not open the file!n“); exit(0); while(!feof(fp) fscanf(fp,“%s“,s);/将读取的主串保存在 s 数组中 printf(“主串为：n%s“,s);/将主串输出到屏幕上 fclose(fp); /求得 nextval 数组的值 void get_nextval(char *t, int nextval) 5 / 8 int j = 1; int k = -1; nextval0 = k; while(tj) if(k = -1) | (tj-1 = tk) if(t+k = tj) nextvalj+ = nextvalk; else nextvalj+ = k; else k = nextvalk; int index_kmp(char s, char t, int next) int c = 0; 6 / 8 int i = 0,j = 0; while(1) while(si /主串循环到下一个 j+;/子串循环到下一个 else j = nextvalj; if(!tj)/如果子串完成一次成功的匹配， i = i - j + 1;/每一次主串的下标 i 回溯到初始位置的下一个，这样就能避 免匹配漏掉； j = 0; /就将子串下标回溯到初始位置 c+;/将记录成功匹配的次数的值加 1，还有，此时主串下标已经向前移动一位， 所以这里不需要再进行 i+ if(!si)/如果主串到达末尾，说明遍历完成，则退出循环 break; 7 / 8 return c;/返回成功匹配的次数 /输出 next 或者 nextval 数组的值 void print_nextval(int nextval, int n) for(int i = 0 ; i n ; i +) printf(“%d “,nextvali); /主函数调用 int main() int index;/定义一个成功匹配的次数的值 char s256,t256;/定义两个字符串数组，来保存主串和子串 write(s);/将主串中的数据读取到 s 数组中 printf(“n 子串为：n“); scanf(“%s“,t);/输出主串 get_nextval(t,nextval);/得到 nextval 数组的值 8 / 8 printf(“改进 nextval 数组元素值为：n“); print_nextval(nextval,strlen(