数据结构—串的模式匹配.doc

实验一 串的模式匹配1. 程序设计简介为简化设计，程序直接利用C+字符数组作为串的存储结构。程序提供显示串（包含主串和模式串）、计算Next、BF匹配、KMP匹配、重建主串、重建模式串等功能。2. 源代码/串模式匹配的类定义FindSub.cpp#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; else return -1;void GetNext(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);/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;coutchoice;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; index=IndexKMP(s,t,next,pos); if(index!=-1) cout模式串在主串的位置从第index个字符开始endl; elsecout主串s中不含模式串tendl; else cout位置非法，无法匹配!endl; break; case 3:/显示NEXT cout子串为：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; default: coutInvalid choicen; break;while(choice!=6);3. 程序运行结果：实验二 求串中最长重复子串1.问题描述 设串S=”s1s2sn”，T=”t1t2tm”，如果TS，则称T为S的子串。设计一算法，求串中最长重复子串。所谓重复，即该子串在串中出现次数多于1次。2.基本要求（1）采用串的顺序存储，设计串的创建方式；（2）设计串中最长重复子串的算法；（3）输入：串可在程序中预设或从键盘读入，或从文件中读入；（4）输出：字符串及最长重复子串。3.源代码#include #include using namespace std; int pipei(string &,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) /匹配成功 do int start=now-str.size(); /匹配成功则尽可能多的并入字符 i=i+1; for(;istart&nown) STR=str; n=STR.size(); str+=si; while(now=pipei(s,str,now); else if(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; else i=i-j+1; j=0; if(j=s2.size()return i; return 0; 4.运行结果总结与体会：这次数据结构的实践，实践