KMP算法复杂度和简单比较.doc

3110008344 王扬旭 信计二班 实现字符串匹配的普通匹配算法和KMP算法 #includeiostream #include string.h using namespace std; #define MAXL 255 //可由用户定义的字符串的长度为255（数值自己设置） typedef unsigned char SString[MAXL +1]; int Index(SString S,SString T,int pos) { //按照普通匹配查找方式查找模式串 int i=pos; int j=1,k=1; while(i=S[0] j=T[0]){ if(S[i]==T[j]){ ++i; ++j; } //继续比较后继字符 else { i=i-j+2; j=1; } //指针后退重新开始匹配 k++; } cout普通匹配查找的时间复杂度为kendl; if(jT[0]) return i-T[0]; //匹配成功 else return 0; }//Index void get_next(SString T,int next[]) { //求KMP算法中的next函数值，并存入数组next[] int i=1; next[1]=0; int j=0; while(iT[0]){ if(j==0 || T[i]==T[j]){ ++i; ++j; next[i]=j; } else j=next[j]; } }//get_next int Index_KMP(SString S,SString T,int pos) { //KMP算法的实现过程 int next[MAXL]; int i=pos; int j=1,k=1; while(i=S[0] j=T[0]){ if(j==0 || S[i]==T[j]){ ++i; ++j; } //继续比较后继字符 else{ get_next(T,next); j=next[j]; } //模式串向右移动 k++; } coutKMP匹配查找的时间复杂度为kendl; if(j(int)T[0]) return i-T[0]; //匹配成功 else return 0; }//Index_KMP void main(){ SString T,S; int p,i,j,k1,k2; p=1; cout请输入字符串匹配主串：endl; cinS; cout请输入字符串匹配模式串：endl; cinT; for(i=1;S[i]!=NULL;i++) { S[0]=i； } for(j=1;T[j]!=NULL;j++) { T[0]=j; } //存储字符串 cout普通算法：endl; k1=Index(S,T,p); cout普通匹配算法得模式串位置：k1endl; coutKMP算法：endl; k2=Index_KMP(S,T,p); coutKMP算法得模式串位置：k2endl; } //当匹配位置为0时代表匹配不成功- 实验结果和数据处理 （1）程序运行时，输入主串为 S=’qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqvbn ‘； 模式串为T=’qqqqqqqqqqqqqqqqqqqqqqqqqvbn’； 运行界面如下： 小结：得到普通匹配算法的时间复杂度为440，而KMP算法的时间复杂度为66，显然在匹配算法中，KMP算法优于普通算法，节省了时间以及资源。 （2）当输入主串为S=’asdfghjlklzxcvbnmqwertyuiop’； 模式串为T=qwertyui’ 运行结果如下： 小结：当匹