欢迎来到天天文库
浏览记录
ID:52199592
大小:126.00 KB
页数:6页
时间:2020-03-24
《数据结构—串的模式匹配.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(j3、=-14、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(i6、j==-17、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,n9、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<
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(i6、j==-17、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,n9、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<
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<
11、"KMP匹配结果:"<12、t';if((j+1)%5==0)cout<
12、t';if((j+1)%5==0)cout<
此文档下载收益归作者所有