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

./数据结构实验报告评分评分满分——5分学号：2015111898姓名：许明华专业：计算机科学与技术知识范畴：字符串完成日期：2017年4月14日实验题目：基于改进KMP算法的字符文件子串查找实验内容及要求：从键盘输入字符文件名以及子串,用改进KMP算法在字符文件中实现子串查找。要求程序输出子串的改进nextval数组元素值以及子串在文件中成功匹配的次数〔查找失败输出成功匹配次数为0。实验目的：掌握子串查找的KMP算法。数据结构设计简要描述：序言：这是本学期第四个实验,本实验是要求我们将一个文件中的字符串读取出来,并自己从键盘上输入一个字符串来进行匹配,并用kmp算法来进行字符串的匹配查找；数据结构简单设计：本实验主要可分为三大模块,第一,从文件中读取出主串,并将其保存在一个字符数组中；第二,通过我们从键盘上输入的字符串来获得改进的nextval数组,而在改进的nextval数组求值算法中,变量还是跟踪的是next数组的值；第三,利用kmp算法来进行主串〔char*s和模式子串〔char*t的匹配,并求出成功匹配的次数；算法设计简要描述：1,求nextval数组的值,我们将不需要用到next数组就可以直接求出nextval数组的值,使nextval得出示值为-1,即nextval[0]=k=-1;将子串下标j初始化为1,然后通过t[j]和t[k]的值变化来获得nextval数组的值,其中的要点是,k值跟踪的仍然是未改进的next[j]的值；2,利用kmp算法来进行主串和模式子串的匹配,定义一个记录匹配的变量c=0,主串下标为i=0,子串下标j=0,当主串和子串第一个元素匹配成功后,进行i++和j++操作,都遍历到下一个元素；当进行一次成功匹配时,将子串的下标回溯到初始位置,记录变量c++,此时主串下标已经到达匹配成功的下一个元素,再继续进行匹配,知道主串到达末尾,结束匹配。输入/输出设计简要描述：1,输入：输入存储主串的文件名,输入子串；2,输出：当输入文件名后,会打印输出主串；当输入子串后,会打印输出nextval数组的值以及匹配成功的次数值c。编程语言说明：编程软件,CodeBlocks16.0；代码均用C语言实现；输入输出采用C语言的printf和scanf函数；程序注释采用C/C++规范；主要函数说明：voidwrite<char>;//读取主串函数voidget_nextval<char,int>;//获得nextval数组函数intindex_kmp<char,char,int>;//kmp算法函数voidprint_nextval<int,int>;//输出nextval数组函数程序测试简要报告：见截图：1,2,源程序代码：#include<stdio.h>#include<stdlib.h>#include<string.h>intnextval[32]={-999};//定义一个nextval数组,并进行初始化//函数声明voidwrite<chars[]>;//读取主串函数voidget_nextval<char,int>;//获得nextval数组函数intindex_kmp<char,char,int>;//kmp算法函数voidprint_nextval<int,int>;//输出nextval数组函数//从文件中将主串读出来并保存在s[]数组中voidwrite<chars[256]>{charfilename[10];FILE*fp;printf<"请输入文件名：\n">;scanf<"%s",filename>;if<<fp=fopen<filename,"r">>==NULL>{printf<"cannotopenthefile!\n">;exit<0>;}while<!feof<fp>>{fscanf<fp,"%s",s>;//将读取的主串保存在s数组中}printf<"主串为：\n%s",s>;//将主串输出到屏幕上fclose<fp>;}//求得nextval数组的值voidget_nextval<char*t,intnextval[]>{intj=1;intk=-1;nextval[0]=k;while<t[j]>if<<k==-1>||<t[j-1]==t[k]>>if<t[++k]==t[j]>nextval[j++]=nextval[k];elsenextval[j++]=k;elsek=nextval[k];}intindex_kmp<chars[],chart[],intnext[]>{intc=0;inti=0,j=0;while<1>{while<s[i]&&<j==-1||t[j]>>//当主串s[i]不为空并且子串t[j]不为空if<<j==-1>||<s[i]==t[j]>>//如果主串的第一个元素和子串的第一个元素匹配上之后,主串和子串下标均向后移一位{i++;//主串循环到下一个j++;//子串循环到下一个}elsej=nextval[j];if<!t[j]>//如果子串完成一次成功的匹配,{i=i-j+1;//每一次主串的下标i回溯到初始位置的下一个,这样就能避免匹配漏掉；j=0;//就将子串下标回溯到初始位置c++;//将记录成功匹配的次数的值加1,还有,此时主串下标已经向前移动一位,所以这里不需要再进行i++}if<!s[i]>//如果主串到达末尾,说明遍历完成,则退出循环break;}returnc;//返回成功匹配的次数}//输出next或者nextval数组的值voidprint_nextval<intnextval[],intn>{for<inti=0;i<n;i++>{printf<"%d",nextval[i]>;}}//主函数调用intmain<>{intindex;//定义一个成功匹配的次数的值chars[256],t[256];//定义两个字符串数组,来保存主串和子串write<s>;//将主串中的数据读取到s数组中printf<"\n子串为：\n">;scanf<"%s",t>;//输出主串get_nextval<t,nextval>;//得到nextval数组的值printf<"改进nextval数组元素值为：\n">;print_nextval<next