簡單匹配算法和KMP算法

1、 實現(xiàn)字符串匹配的簡單匹配算法和KMP算法，并且使用相同的比較字符串重復(fù)比較至少5000次，計算兩者的時間差別。實驗要求：完成實驗內(nèi)容要求，編寫程序?qū)崿F(xiàn)。提交報告，報告分三部分內(nèi)容：1） 自己是怎么做的？遇到什么問題，怎樣解決的？2） 用了哪些數(shù)據(jù)，得到什么結(jié)果？程序結(jié)果是不是跟你想的一樣？為什么不一樣？3） 還有哪些值得改進(jìn)或者不懂的？一、 實驗方案源程序的頭文件定義為：#include #include #include #include 又作出以下宏定義方便編程：#define OVERFLOW -2#define OK 1#define MAXSTRLEN 255源程序中的各個函數(shù)原型

2、如下所示：typedef char SStringMAXSTRLEN+1;int Index(SString S,SString T,int pos) /按照普通匹配查找方式查找模式串int i=pos;int j=1,k=0;while(i=(int)S0 & jT0) return i-T0;else return 0;/Indexvoid get_next(SString T,int next) /求KMP算法中的next函數(shù)值，并存入數(shù)組next int i=1; next1=0; int j=0; while(i(int)T0) if(j=0 | Ti=Tj) +i; +j; if(

3、Ti!=Tj) nexti=j; else nexti=nextj; else j=nextj; /nextint Index_KMP(SString S,SString T,int pos) /KMP算法的實現(xiàn)過程int nextMAXSTRLEN;int i=pos;int j=1,k=0;while(i=(int)S0 & j(int)T0)return i-T0;else return 0;/Index_KMP源程序中主函數(shù)如下：void main()SString T,S;int p,i,j,k1,k2;p=1;i=1;j=1;printf(請輸入字符串匹配主串：n);gets(&S

4、1);printf(請輸入字符串匹配模式串：n);gets(&T1);for(i=1;Si!=NULL;i+)S0=(int)(i);printf(字符串匹配中主串：n);puts(&S1);for(j=1;Tj!=NULL;j+)T0=(int)(j);printf(n字符串匹配中模式串：n);puts(&T1); printf(普通算法n);k1=Index(S,T,p);printf(普通匹配算法得模式串位置：%dnn,k1);printf(KMP算法n);k2=Index_KMP(S,T,p);printf(KMP算法得模式串位置：%dn,k2);二、 實驗結(jié)果和數(shù)據(jù)處理（1）程序運(yùn)行

5、時，輸入主串為S=qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqws ；模式串為T=qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqws；運(yùn)行界面如下：小結(jié)：得到普通匹配算法的時間復(fù)雜度為3793，而KMP算法的時間復(fù)雜度為174，顯然在匹配算法中，KMP算法優(yōu)于普通算法，節(jié)省了時間以及資源。（2）當(dāng)輸入主串為S=A STRING SEARCHING EXAMPL