《数据结构—串的模式匹配》由会员分享，可在线阅读，更多相关《数据结构—串的模式匹配（6页珍藏版）》请在金锄头文库上搜索。
1、实验一实验一 串的模式匹配串的模式匹配1.程序设计简介为简化设计，程序直接利用C+字符数组作为串的存储结构。程序提供显示串包含主串和模式串 、计算 Next、BF 匹配、KMP 匹配、重建主串、重建模式串等功能。2.源代码#include#include#include#include#includeconst maxsize=30;int IndexBF(char s,char t,int pos)int i,j,m,n;i=pos-1;j=0;m=strlen(s);n=strlen(t);while(im & j=n)return i-n+1;elsereturn -1;void Get
2、Next(char t,int next)/ 求模式串 T 的 next 函数值并存入数组 nextint j=0,k=-1;int n=strlen(t);nextj=-1;while(jn)if(k=-1|tj=tk)j+;k+;nextj=k;else k=nextk;int IndexKMP(char s,char t,int next,int pos)/ 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置的 KMP 算法。/ 其中,T 非空,1posStrLength(S)int i,j,n;i=pos-1;j=0;int m=strlen(s);/
3、sm=0;n=strlen(t);/tn=0;while(im & j=n) return i-n+1;/ 匹配成功return -1;/串模式匹配的测试void main()char smaxsize=aaabaaaabaa,tmaxsize=aaaab;int index,*next;int choice,j,pos=0;int m,n;m=strlen(s);n=strlen(t);next=new intn;GetNext(t,next);do/显示主菜单cout1-BF 匹配n;cout2-KMP 匹配n;cout3-查看 Nextn;cout4-显示串n;cout6-退出n;cou
4、tchoice;switch(choice)case 1:/BF 匹配coutpos;if(pos=m-n+1)cout主串为:st子串为:tendl;coutBF 的结果:endl;index=IndexBF(s,t,pos);if(index!=-1)cout模式串 t 在主串 s 中的位置从第index个字符开始endl;else cout主串 s 中不含模式串 tendl;else cout位置非法，无法匹配!endl; break;case 2:/KMP 算法coutpos;if(pos=m-n+1)cout主串为:st子串为:tendl;coutKMP 匹配结果:endl;inde
5、x=IndexKMP(s,t,next,pos);if(index!=-1)cout模式串在主串的位置从第index个字符开始endl;elsecout主串 s 中不含模式串 tendl;else cout位置非法，无法匹配!endl; break;case 3:/显示 NEXTcout子串为：tendl;for(j=0;jn;j+)coutnextj=nextjt;if(j+1)%5=0) coutendl;coutendl;break;case 4: /显示串cout主串为：s;cout子串为: t;coutendl;break;case 6:/退出cout结束运行!endl;break;
6、default:coutInvalid choicen;break;while(choice!=6);3.程序运行结果：实验二实验二求串中最长重复子串求串中最长重复子串1.问题描述设串 S=”s1s2sn”，T=”t1t2tm”，如果 TS，则称T 为 S 的子串。设计一算法，求串中最长重复子串。所谓重复，即该子串在串中出现次数多于1 次。1采用串的顺序存储，设计串的创建方式；2设计串中最长重复子串的算法；3输入：串可在程序中预设或从键盘读入，或从文件中读入；4输出：字符串及最长重复子串。#include#includeusing namespace std;int pipei(string
7、&,string &,int );using namespace std;void main()string s;int n=0;string STR; /STR存储当前最长的字符串cout请输入一个字符串：s;string str=;str=str+s0;for(int i=0;is.size()-1;)if(int now=pipei(s,str,i+1)/匹配成功doint start=now-str.size(); /匹配成功则尽可能多的并入字符i=i+1;for(;istart&nown)STR=str;n=STR.size();str+=si;while(now=pipei(s,s
8、tr,now);elseif(str.size()=1)i+;str=si;cout最长重复子串为：STRendl;cout长度是:nendl;getchar();getchar();getchar();int pipei(string &s1,string &s2,int i)int j=0;while(is1.size()&js2.size()if(s1i=s2j)+i;+j;elsei=i-j+1;j=0;if(j=s2.size()return i;return 0;总结与体会：这次数据结构的实践，实践完后颇有收获。数据结构更加注重设计灵活、巧妙的算法，提高程序运行效率，这对我逻辑思维能力的提高有相当大的帮助。 进行数据结构的编程， 程序调试过程中遇到了很多的问题， 经过问老师问同学查资料等等一系列努力， 终于调试出了结果，也大大的鼓舞了我，培养了我的耐心恒心。
