《串的模式匹配》由会员分享，可在线阅读，更多相关《串的模式匹配（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告所在院系:名：指导老师:实验报告实验串的模式匹配姓名：班 级：学号：试验时间：1、问题描述程序定义了一个串类。该串类中，串数据成员有两个。程序在初始化中，对主串、子串 已赋值， 用户在启动程序后，可通过菜单选项进行查看。 如果要创建新的主串和子串， 通过菜单选项进行。2、算法设计源程序：/串模式匹配的类定义 Fin dSub.cpp#i nclude#in clude#in clude#in clude#in cludeconst maxsize=30;int In dexBF(char s,char t,i nt pos)int i,j,m, n;i=pos-1;j=0;m=
2、strle n(s);n=strle n(t);while(im & j=n)return i-n+1;elsereturn -1; void GetNext(char t,i nt n ext)求模式串 T 的 next 函数值并存入数组nextint j=0,k=-1;int n=strle n(t);n extj=-1;while(j n)if(k=-1|tj=tk)j+；k+; nextj=k;else k=n extk;int In dexKMP(char s,char t,i nt next,i nt pos)利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP
3、算法。 / 其中,T 非空,1 posw StrLength(S)int i,j,n;i=pos-1;j=0;int m=strle n( s);sm=0：n=strle n(t);t n=0：while(im & j=n) return i-n+1;/ 匹配成功 return -1;/串模式匹配的测试void mai n() char smaxsize=aaabaaaabaa,tmaxsize=aaaab;int in dex,* next;int choice,j,pos=0;int m,n;m=strle n(s);n=strle n(t);n ext=new intn;GetNext(
4、t ,n ext);do/显示主菜单cout1-BF 匹配 n;cout2-KMP 匹配 n;coutvv3-查看 Nextn;coutvv4-显示串 n;coutvv6-退出 n;cout choice;switch(choice)case 1:/BF 匹配coutvv输入匹配起始位置：；cin pos;if(pos=m-n+1)coutvv主串为:vvsvvtvv子串为:vvtvvendl; coutvvBF 的结果:vvendl; in dex= In dexBF(s,t,pos);if(in dex!=-1) pos;if(posv=m-n +1)coutvv主串为:vvsvvtvv子
5、串为:vvtvvendl; coutvvKMP 匹配结果:vvendl; in dex= In dexKMP(s,t ,n ext,pos); if(i ndex!=-1)coutvv模式串在主串的位置从第vvindexvv个字符开始vvendl;elsecoutvv主串s中不含模式串tvvendl;else coutvv位置非法，无法匹配!vvendl;break;case 3:/显示 NEXTcoutvv子串为：vvtvvendl;for(j=0;jv n;j+)coutvv nextvvjvv=vv nextjvvt;if(j+1)%5=0) coutvve ndl; coute ndl
6、; break;case 4: 显示串 coutvv主串为：vvs; coutvv子串为:vvt; coutvve ndl; break; case 6:/退出 coutvv结束运行!endl; break;default:coutvvI nvalid choicen; break; while(choice!=6);3 、运行与测试程序启动界面如图所示。Hextt1tntep cho卜-BF匹配2- KMPC3- 查看 彳-显石学习JStS:f5jS5_FindStrDebugFindStRexeCasel :输入1,选择菜单1,进行朴素匹配操作。屏幕显示朴素（BF）匹配结果。Case2:输
7、入2,选择菜单2,进行KMP匹配操作。屏幕显示KMP匹配结果。Case3:输入3,选择菜单3,进行求Next操作。屏幕显示Next啲值。Case4:输入4，选择菜单4，进行串内容显示操作。屏幕显示主串、子串内容。Case6:输入6，选择菜单6，结束程序运行。4 、思考题1 )创建若干组主串和子串，运行程序，记录 分 Next 、BF匹配和KMP匹配结果，并 析运行结果的正确性。答：BF匹配结果：j : MM5_AFindStrDebugFindStrexeRA KM 熙 Xoi- fc显七t 显输入一串:jBF入蛋c二 模串 -E配 黒 a己L-BF$-KUP匹酉己JJ He xt 1I-显平
8、串A退出inter clio ice : 2啟爭配起始粒置m十串力 :aaaab主串为 :aaabaaaabaaCP匹|己结熙厦式审在圭串的位置从第5个字符开始Next:：S5l据结构实苦卩-串F ind StrDe bugFmd回2- KMPlJt 酉己 A 查看 Next!4-显平串退出Enter choice子串为：2)在程序的适当位置添加计数器， 分别统计两种匹配算法的匹配趟数， 分析算法性能。 答：朴素模式匹配算法匹配失败重新比较时只能向前移二个字符，若主串中存在和模式串只有部分匹配的多个子串， 匹配指针将多次回溯， 而回溯次数越多算法的效率越低， 它的时 间复杂度一般情况下为 0(
9、n-m+1)m),最坏的情况下为0(m*n),最好的情况下为0(m+n)。KMP莫式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中 出现失配时，不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符， 过滤掉那些多 余的比较，将模式串向右“滑动”尽可能远的一段距离后， 继续进行比较，从而提高模式匹配的效率，该算法的时间复杂度为 0(m+n)。5 、心得体会实践是检验真理的唯一标准，通过实践，我们能更好的掌握课本上的知识， 把理论和实 际结合起来，方便我们把学到的知识用到实际生活中去， 更好的解决实际生活中遇到的问题。通过对本次实验的验证，我对于串这一概念有了更进一步的认识，同时也更了解了 BF 匹配、KMP匹配等算法的运行过程和结果，同时也更加直观的了解了子串在主串中的匹配 过程，收 获很大。
