模式匹配算法的设计与实现

-五、详细设计#includestring#includefstream#includecstdlib#includetime.husingnamespacestd;#defineMAX100000#defineM69classString{private:intn;char*str;int*count;//记录子串在主串中出现的位置intFind(inti,String&P);//简单匹配算法找到最近的匹配串后立即停止，而不向下继续且缺乏一个数组记录位置int*f;//记录失败函数voidFail();intKMPFind(inti,String&P);//改进的失败函数voidImproveFail();intKMPFindImprove(inti,String&P);public:String();//建立一个空串String(constchar*p);String(constString&p);//拷贝函数~String();intLength(){returnn;};//返回当前串对象长度voidOutput(){coutstr;};//输出字符串intFind(String&P);//简单匹配算法intKMPFind(String&P);//KMP匹配算法-intKMPFindImprove(String&P);//改进的KMP匹配算法voidOutput2();//输出子串在主串中出现的位置};intString::KMPFindImprove(String&P){intsum=0;intj=KMPFindImprove(0,P);while(j!=-1){count[sum++]=j;if(j=n-P.n)j=KMPFindImprove(j+P.n,P);}returnsum;}voidString::Output2()//输出子串在主串中的位置{inti=0;while(count[i]!=count[i+1]&&iMAX-1)//若不再有新的子串匹配，则count[i]与count[i+1]均为0{coutcount[i];i++;}}voidmenu(){cout********************************************endl;coutendl;coutendl;-cout1.简单模式匹配算法endl;coutendl;coutendl;cout2.KMP模式匹配算法endl;coutendl;cout4.退出endl;coutendl;coutendl;cout################################################endl;}voidmain(){intchoice=0;menu();clock_tstart,finish;while(choice!=4)//循环可以连续选择{cout请输入选择endl;cinchoice;if(choice==1){Strings1(ThrougharetrospectivelookatthemathematicsteachingatUSTC,thisarticlesummarizesuniversity'steachingachievementsinpast45years.);-s1.Output();coutendl;Strings2(teaching);start=clock();intm=s1.Find(s2);s2.Output();cout出现的次数为:mendl;if(m!=0){cout匹配的位置是;s1.Output2();coutendl;}finish=clock();coutendltimeis:(double)(finish-start)/CLK_TCKendl;}if(choice==2){clock_tstart,finish;start=clock();Strings1(ThrougharetrospectivelookatthemathematicsteachingatUSTC,thisarticlesummarizesuniversity'steachingachievementsinpast45years.);s1.Output();coutendl;Strings2(teaching);s2.Output();coutendl;intn=s1.KMPFind(s2);cout出现的次数为:nendl;if(n!=0)-{coutn匹配的位置是;s1.Output2();coutendl;}finish=clock();coutendltimeis:(double)(finish-start)/CLK_TCKendl;}if(choice==3){clock_tstart,finish;start=clock();Strings1(ThrougharetrospectivelookatthemathematicsteachingatUSTC,thisarticlesummarizesuniversity'steachingachievementsinpast45years.);s1.Output();coutendl;Strings2(teaching);s2.Output();coutendl;intn=s1.KMPFindImprove(s2);cout出现在主串中的次数为:nendl;if(n!=0){coutn匹配的位置是;s1.Output2();coutendl;}finish=clock();coutendltimeis:(double)(finish-start)/CLK_TCKendl;}}-}