基于改进型KMP算法的字符串查找与替换

《基于改进型KMP算法的字符串查找与替换》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告评分满分——5分学号：2014111962姓名：施永邦专业：计算机科学与技术知识范畴：串完成日期：2016年04月6日实验题目：基于改进型KMP算法的字符串查找与替换实验内容及要求：从键盘输入三个字符串s、a、b,在串s中查找子串a，并将串s中的所有a替换为b，输出替换以后的串。注意：a和b的串长不要求相等；若s中无子串a,输出结果与串s相同。实验目的：掌握字符串模式匹配的KMP算法。数据结构设计简要描述：用char型数组储存串s，a，b。用int型数组储存模式串a的next数组。算法设计简要描述：在串s中查找子串a的起始位置使用了KMP算法。利用get_next

2、val函数得到模式串a的nextval数组。函数replace替换s中的a。用指向s的指针p先指向s起始地址，利用KMP算法得到s中第一个a起始位置，然后用b替换a，替换后p指向第一个a起始位置再向后b的长度，查找第二个a的起始位置，依次类推。输入/输出设计简要描述：按照提示：先输入s串，然后输入a串。如果未找到a，则原样输出s。如果找到第一个a，输出第一个a的位置，并提示输入b，然后会替换剩下的所有a，输出替换后的s，并输出替换次数。编程语言说明：使用VisualC++编程。主要代码采用C语言实现；动态存储分配采用C++的new和delete操作符实现；输入与输出采用C++的c

3、in和cout流；程序注释采用C/C++规范。主要函数说明：voidget_nextval(char*t,intnextval[]);//get_nextval函数intindex_kmp(char*s,char*t,intnext[]);//KMP算法voidreplace(char*s,char*b,intposition,intlena);//替换字符串函数://b的长度大于a的情况下先将s中a后边的所有字符向后挪动lenb-lena个位置//b的长度小于a的情况下先将s中a后边的所有字符向前挪动lena-lenb个位置//然后将a的字符逐个用b中的字符替换程序测试简要报告

4、：(1)无a测试4/4程序输入输出结论程序输出结果与期望输出结果相符。(1)a、b等长度测试程序输入输出结论程序输出结果与期望输出结果相符。(2)a、b不等长度测试程序输入输出4/4结论程序输出结果与期望输出结果相符。源程序代码：#include#includeusingnamespacestd;voidget_nextval(char*t,intnextval[]){//get_nextval函数intj=1,k=-1;nextval[0]=-1;while(t[j]){if(k==-1

5、

6、t[j-1]==t[k])if(t[++k]==t

7、[j])nextval[j++]=nextval[k];elsenextval[j++]=k;elsek=nextval[k];}}intindex_kmp(char*s,char*t,intnext[]){//KMP查找函数inti=0,j=0;while(s[i]&&t[j]){if(j==-1

8、

9、s[i]==t[j]){i++;j++;}elsej=next[j];}if(!t[j])returni-j;return-1;}voidreplace(char*s,char*b,intposition,intlena){inti,j,lens=strlen(s),lenb=st

10、rlen(b);if(lenb>lena){//将a以后的字符串向后挪lenb-lena个位置for(i=lens+lenb-lena,j=lens;j>=position+lena;i--,j--)s[i]=s[j];}elseif(lenb

11、intnext[40],count=0;while(1){cout<<"InputS:";cin>>s;p=s;cout<<"InputA:";cin>>a;get_next(a,next);while(strlen(p)>=strlen(a)){//剩余字符串长度小于p时停止查找intposition=index_kmp(p,a,next);if(position==-1)break;count++;//count计找到a的次数if(count==1){//找到第一个a