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

《数据结构—串的模式匹配.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验一串的模式匹配1.程序设计简介为简化设计，程序直接利用C++字符数组作为串的存储结构。程序提供显示串（包含主串和模式串）、计算Next[]、BF匹配、KMP匹配、重建主串、重建模式串等功能。2.源代码//串模式匹配的类定义FindSub.cpp#include#include#include#include#includeconstmaxsize=30;intIndexBF(chars[],chart[],i

2、ntpos){inti,j,m,n;i=pos-1;j=0;m=strlen(s);n=strlen(t);while(i=n)returni-n+1;elsereturn-1;}voidGetNext(chart[],intnext[]){//求模式串T的next函数值并存入数组nextintj=0,k=-1;intn=strlen(t);next[j]=-1;while(j

3、=-1

4、

5、t[j]==t[k]){j++;k++;next[j]=k;}elsek=next[k];}}intIndexKMP(chars[],chart[],intnext[],intpos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。//其中,T非空,1≤pos≤StrLength(S)inti,j,n;i=pos-1;j=0;intm=strlen(s);//s[m]='';n=strlen(t);//t[n]='';while(i

6、j==-1

7、

8、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,n

9、ext);do{//显示主菜单cout<<"1-BF匹配";cout<<"2-KMP匹配";cout<<"3-查看Next[]";cout<<"4-显示串";cout<<"6-退出";cout<<"Enterchoice:";cin>>choice;switch(choice){case1://BF匹配cout<<"输入匹配起始位置:";cin>>pos;if(pos<=m-n+1){cout<<"主串为:"<

10、"<>pos;if(pos<=m-n+1){cout<<"主串为:"<

11、"KMP匹配结果:"<

12、t';if((j+1)%5==0)cout<