下载文档原格式
数据结构一串的模式匹配实验一串的模式匹配1.程序设计简介为简化设计，程序直接利用C++字符数组作为串的存储结构。
程序提供显示串(包含主串和模式串)、计算Next[]、BF匹配、KMP匹配、重建主串、重建模式串等功能。
2.源代码〃串模式匹配的类定义Fin dSub.cpp#in cludevioma nip.h>#in cludevstri ng.h>#in clude<stdio.h>#in clude<stdlib.h>#in cludevstri ng>const maxsize=30;int In dexBF(char s[],char t[],i nt pos){int i,j,m, n;i=pos-1;j=0;m=strle n( s);n=strle n(t);while(i<m && j<n){if(s[i]==t[j]){++i；++j；}else {i=i-j+1;j=0;}}if(j>=n)return i-n+1;elsereturn -1;}void GetNext(char t[],i nt next[]){//求模式串T的next函数值并存入数组next in t j=0,k=-1;int n=strle n(t);n ext[j]=-1;while(j <n){if(k==-1||t[j]==t[k]){j++;k++; next[j]=k;}else k=n ext[k];}int IndexKMP(char s[],char t[],int next[],int pos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。
// 其中,T 非空,1 < pos< StrLength(S) in t i,j, n;i=pos-1;j=0;int m=strle n( s);〃s[m]='\0：n=strle n(t);//t[ n]='\0：while(i<m && jvn)if(j==-1||s[i]==t[j]){i++；j++；}〃继续比较后继字符else j=next[j];//模式串向右移动if(j>=n) return i-n+1;// 匹配成功return -1;}〃串模式匹配的测试void mai n(){ char s[maxsize]="aaabaaaabaa",t[maxsize]="aaaab"int in dex,* nex t;int choice,j,pos=0;int m,n;m=strle n( s);n=strle n(t);n ext=new int[n];GetNext(t, next);do{//显示主菜单cout«"1-BF 匹配\n";cout«"2-KMP 匹配\n";cout<<"3-查看Next[]\n";cout<<"4-显示串\n";cout<<"6-退出\n";cout«"E nter choice:";cin> >choice;switch(choice){case 1://BF 匹配cout<<"输入匹配起始位置："cin> >pos;if(pos<=m-n+1)coutvv"主串为:"vvs<v'\t'vv" 子串为:"vvtvvendl;cout«"BF 的结果:"<<endl;in dex=In dexBF(s,t,pos);if(in dex!=-1)cout<<"模式串t在主串s中的位置从第"<<index<<"个字符开始"<<endl;else cout<<"主串s中不含模式串t"<<e ndl;}else{ cout<<"位置非法，无法匹配!"<<e ndl; }break;case 2://KMP 算法cout<<"输入匹配起始位置："；cin> >pos;if(pos<=m-n+1){cout<<"主串为:"<<s<<'\t'<<" 子串为:"vvtvvendl;cout«"KMP 匹配结果:"<<endl;in dex=I ndexKMP(s,t, next,pos);if(in dex!=-1)cout<<"模式串在主串的位置从第"<<index<<"个字符开始"<<endl;elsecout<<"主串s中不含模式串t"<<e ndl;}else{ cout<<"位置非法，无法匹配!"<<e ndl; }break;case 3://显示NEXTcout<<"子串为："<<t<<endl;for(j=0;j< n;j++){cout<<" next["<<j<<"]="<< next[j]<<'\t';if((j+1)%5==0) cout<<e ndl;}cout«e ndl; break;case 4: /湿示串cout«"主串为："<<s;cout«"子串为:"<<t;cout«e ndl;break;case 6://退出cout«"结束运行!"<<endl; break;default:cout<v"lnvalid choice'n"; break;}}while(choice!=6);}3.程序运行结果:实验二求串中最长重复子串1•问题描述设串 S=”1s2 sn " , T= ”1t2 ......... tm ” 如果 rr + +\M^Dev^^Mytro ^1127 .De bug\201 i 1127A予禺为:aaaab 了 昌为=d4d4b next tl1-0 next[2J-l next(31-2 next[41-3ncm HIT %■11N ；"』”【 帥wJHT € S,则称T为S的子串。
L4.3 串的模式匹配算法⏹定义子串的定位操作通常称做串的模式匹配(其中P、T称为模式串，P a T tern），是各种串处理系统中最重要的操作之一。
⏹名词在串的模式匹配中，子串P称为模式，主串S称为目标。
【示例】目标S : “Beijing”模式P : “jin”匹配结果= 3（匹配位置从0 开始）☐讨论两种匹配算法：BF 算法和KMP 算法。
4.3.1 求子串位置的定位函数初始时让目标S 的第0 位与模式P 的第0 位对齐；顺序比对目标S 与模式P 中的对应字符：❒若P 与S 比对发现对应位不匹配，则本趟失配。
将P 右移一位与S 对齐，进行下一趟比对；❒若P 与S 对应位都相等，则匹配成功，返回S 当前比较指针停留位置减去P 的长度，即目标S 中匹配成功的位置，算法结束。
❒若P 与S 比对过程中，S 后面所剩字符个数少于P 的长度，则模式匹配失败。
Brute-Force 简称为BF 算法，亦称简单匹配算法。
采用穷举的思路。
LBF 算法匹配过程的示例第1趟S a b b a b aP a b a 第2趟S a b b a b aP a b ai=2j=2i=1j=0第3趟S a b b a b a P a b a第4趟S a b b a b a P a b ai=2j=0i=6j=3这是最简单的模式匹配算法。
Lint index(SqString S, SqString P, int pos)L{int i = pos -1, j = 0;while(i < S.length && j < P.length) {if(S.SString[i] == P.SString[j]) {i++;//主串和子串依次匹配下一个字符j++;}else { //主串、子串指针回溯重新开始下一次匹配i = i -j + 1; //主串从下一个位置开始匹配j = 0; //子串从头开始匹配}}if(j >= P.length)return(i -P.length);//返回匹配的第一个字符的下标elsereturn -1;//模式匹配不成功}☐若设n 为目标S 的长度，m 为模式P 的长度，匹配算法最多比较n -m +1趟。
