簡(jiǎn)單匹配算法和KMP算法

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

4、1);printf(請(qǐng)輸入字符串匹配模式串：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);二、 實(shí)驗(yàn)結(jié)果和數(shù)據(jù)處理（1）程序運(yùn)行

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