1、五、詳細(xì)設(shè)計 #include#include#include#includeusing namespace std;#define MAX #define M 69class Stringprivate:int n;char *str;int *count; /記錄子串在主串中出現(xiàn)的位置 int Find(int i,String &P); / 簡單匹配算法 找到最近的匹配串后立即停止，而不向下繼續(xù)且缺乏一個數(shù)組記錄位置int *f ; /記錄失敗函數(shù)void Fail(); int KMPFind(int i,String &P); /改進(jìn)的失敗函數(shù)void ImproveFail();i

2、nt KMPFindImprove(int i,String &P); public: String(); /建立一個空串String(const char *p);String(const String &p); /拷貝函數(shù)String();int Length() return n; /返回當(dāng)前串對象長度void Output() coutstr; /輸出字符串int Find(String &P); /簡單匹配算法int KMPFind(String &P); /KMP匹配算法int KMPFindImprove(String &P); /改進(jìn)的KMP匹配算法 void Output2(

3、); /輸出子串在主串中出現(xiàn)的位置;int String:KMPFindImprove(String &P)int sum=0; int j=KMPFindImprove(0,P);while(j!=-1)countsum+=j;if(j=n-P.n) j=KMPFindImprove(j+P.n,P);return sum; void String:Output2() /輸出子串在主串中的位置 int i=0;while(counti!=counti+1 & iMAX-1) /若不再有新的子串匹配，則counti與counti+1均為0coutcounti ;i+; void menu()c

4、out*endl;coutendl;coutendl; cout 1.簡單模式匹配算法endl;coutendl;coutendl;cout 2.KMP模式匹配算法endl;coutendl;cout 4.退出endl;coutendl;coutendl;cout#endl; void main() int choice=0; menu(); clock_t start,finish;while(choice!=4)/循環(huán)可以連續(xù)選擇cout請輸入選擇choice; if(choice=1) String s1(Through aretro spectivelook at the mathe

5、matics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.);s1.Output(); coutendl;String s2(teaching);start=clock();int m=s1.Find(s2); s2.Output();cout出現(xiàn)的次數(shù)為:mendl;if(m!=0) cout匹配的位置是;s1.Output2();coutendl;finish=clock();coutendltime is:(double)(finish-start

6、)/CLK_TCKendl;if(choice=2) clock_t start,finish;start=clock();String s1(Through a retrospective look at the mathematics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.);s1.Output(); coutendl;String s2(teaching);s2.Output(); coutendl;int n=s1.KMPFind(s2);

7、cout出現(xiàn)的次數(shù)為:nendl;if(n!=0)coutn匹配的位置是;s1.Output2();coutendl;finish=clock();coutendltime is:(double)(finish-start)/CLK_TCKendl;if(choice=3) clock_t start,finish;start=clock();String s1(Through a retrospective look at the mathematics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.);s1.Output(); coutendl;String s2(teaching);s2.Output(); coutendl;int n=s1.KMPFindImprove(s2);cout出現(xiàn)在主串中的次