数据结构-串的模式匹配

实验一串的模式匹配1.程序设计简介为简化设计，程序直接利用C++字符数组作为串的存储结构。程序提供显示串〔包含主串和模式串〕计算Next[]、BF匹配、KMP匹配、重建主串、重建模式串等功能。2.源代码//串模式匹配的类定义FindSub.cpp#include<iomanip.h>#include<string.h>#include<stdio.h>#include<stdlib.h>#include<string>constmaxsize=30;intIndexBF(chars[],chart[],intpos){inti,j,m,n;i=pos-1;j=0;m=strlen(s);n=strlen(t);while(i<m&&j<n){if(s[i]==t[j]){++i;++j;}else{i=i-j+1;j=0;}}if(j>=n)returni-n+1;elsereturn-1;}voidGetNext(chart[],intnext[]){〃求模式串T的next函数值并存入数组nextintj=O,k=-l;intn=strlen(t);next[j]=-l;while(j<n){if(k==-l||t[j]==t[k]){j++;k++;next[j]=k;}elsek=next[k];}}intIndexKMP(chars[],chart[],intnext[],intpos){〃利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。//其中,T非空,1WposWStrLength(S)inti,j,n;i=pos-1;j=0;intm=strlen(s);//s[m]='\0';n=strlen(t);//t[n]='\0';while(i<m&&j<n)if(j==-1||s[i]==t[j]){i++;j++;}//继续比拟后继字符elsej=next[j];//模式串向右移动if(j>=n)returni-n+1;//匹配成功return-1;}//串模式匹配的测试voidmain(){chars[maxsize]="aaabaaaabaa",t[maxsize]="aaaab";intindex,*next;intchoice,j,pos=0;intm,n;m=strlen(s);n=strlen(t);next=newint[n];GetNext(t,next);do{//显示主菜单coutvv"1-BF匹配\n";coutvv"2-KMP匹配\n";coutvv"3-查看Next[]\n";coutvv"4-显示串\n";coutvv"6-退出\n";cout<<"Enterchoice:";cin>>choice;switch(choice){case1://BF匹配coutvv"输入匹配起始位置:"；cin>>pos;if(pos<=m-n+1){coutvv"主串为:"vvsvv'\t'vv"子串为:"vvtvvendl;coutvv"BF的结果:"vvendl;index=IndexBF(s,t,pos);if(index!=-1)coutvv"模式串t在主串s中的位置从第"vvindexvv"个字符开始"vvendl;elsecoutvv"主串s中不含模式串t"vvendl;}else{coutvv"位置非法，无法匹配!"vvendl;}break;case2://KMP算法coutvv"输入匹配起始位置:"；cin>>pos;if(posv=m-n+1){coutvv"主串为:"vvsvv'\t'vv"子串为:"vvtvvendl;coutvv"KMP匹配结果:"vvendl;index=IndexKMP(s,t,next,pos);if(index!=-1)coutvv"模式串在主串的位置从第"vvindexvv"个字符开始"vvendl;elsecoutvv"主串s中不含模式串t"vvendl;}else{coutvv"位置非法，无法匹配!"vvendl;}break;case3://显示NEXTcoutvv"子串为："vvtvvendl;for(j=0;jvn;j++){coutvv"next["vvjvv"]="vvnext[j]vv'\t';if((j+1)%5==0)coutvvendl;}coutvvendl;break;case4://显示串coutvv"主串为："vvs;coutvv"子串为："vvt;coutvvendl;break;case6://退出coutvv"完毕运行!"vvendl;break;default:coutvv"Invalidchoice\n";break;

}while(choice!=6);}3.程序运行结果:实验二求串中最长重复子串1•问题描述设串S=〃s1s2……sn〃，T=〃t1t2……tm〃，如果T^S,那么称T为S的子串。设计一算法，求串中最长重复子串。所谓重复，即该子串在串中出现次数多于1次。2.根本要求〔1〕采用串的顺序存储，设计串的创建方式；〔2〕设计串中最长重复子串的算法；〔3〕输入：串可在程序中预设或从键盘读入，或从文件中读入；〔4〕输出：字符串与最长重复子串。3.源代码#include<iostream>#include<string>usingnamespacestd;intpipei(string&,string&,int);usingnamespacestd;voidmain(){strings;intn=0;stringSTR;//STR存储当前最长的字符串coutvv"请输入一个字符串："vvendl;cin>>s;stringstr="";str=str+s[0];for(inti=0;ivs.size()-1;){if(intnow=pipei(s,str,i+1)){ //匹配成功do{intstart=now-str.size();//匹配成功那么尽可能多的并入字符i=i+1;for(;ivstart&&nowvs.size()&&s[i]==s[now];i++,now++)str+=s[i];if(str.size()>n){STR=str;n=STR.size();}str+=s[i];}while(now=pipei(s,str,now));}else{if(str.size()==1){i++;}str=s[i];}}coutvv"最长重复子串为："vvSTRvvendl;coutvv"长度是:"vvnvvendl;getchar();getchar();getchar();}intpipei(string&s1,string&s2,inti){intj=0;while(ivsl.size()&&jvs2.size()){if(sl[i]==s2[j]){++i；++j；}else{i=i-j+1；j=0；}if(j==s2.size())returni;}return