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

《KMP算法复杂度与简单比较.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途　　3１1０008３44　王扬旭　信计二班实现字符串匹配的普通匹配算法和ＫMP算法#includｅ＜ｉoｓtream＞#iｎｃlｕdeusingnamｅspaｃe　std;＃defineMAXL2５５//可由用户定义的字符串的长度为255（数值自己设置）typedefuｎsｉgnｅdcharSStrinｇ[MAXL　+1];intＩnｄex(SStrｉng　S,SSｔringT,ｉntｐｏs)｛　　　　　　　　　／／按照普通匹配查找方式查找模式串ﻩinｔｉ=poｓ;ﻩintj=１,k=１;whｉle(i＜=S[0]&&ｊ<=T[0]）{ﻩｉf

2、(Ｓ[i］==Ｔ[ｊ]){ﻩ++ｉ；ﻩﻩ＋＋j;ﻩ}　　　　　　//继续比较后继字符ﻩelsｅﻩﻩ{ﻩﻩｉ=i-j+2;j=1;ﻩ}　　　　　//指针后退重新开始匹配ﻩk＋+；ﻩ}ﻩcout<<"普通匹配查找的时间复杂度为"<T[0])ﻩﻩrｅturni-Ｔ［0］;　　　　/／匹配成功ﻩelserｅtuｒn0;｝／/Indｅｘvoｉdget＿nexｔ（ＳStringT，intnext[]）{　　　　　　　　　　／/求ＫMP算法中的nｅｘt函数值，并存入数组ｎext[]　ｉnｔi=1;ﻩｎｅxｔ[1]=0;ｉntj=0;ﻩｗhiｌe(ｉ

3、j==０｜

4、T[ｉ]==Ｔ[ｊ]）｛　++ｉ;ﻩﻩ++j;ﻩﻩﻩnext[ｉ]＝j;ﻩ}ﻩeｌｓe　j＝next[j］;ﻩ　｝个人收集整理勿做商业用途}//get_nexｔiｎtIndex_KMP(ＳStｒingＳ,SＳｔringT，int　pos）{　　　　　　　　　　　　　//KMP算法的实现过程intnext［ＭAＸＬ］；ﻩinｔi＝ｐos；ﻩintj=1,k=１;wｈｉle(i<=S[0］&&ｊ<＝T［0]){ﻩﻩif(j＝=0

5、

6、S［i］==T[j]){ﻩ＋+i;ﻩ++j;ﻩ}　　　　　　　　　//继续比较后继字符ﻩelｓe｛ﻩﻩgｅt_ｎｅxt(Ｔ，ｎext);ﻩj＝nex

7、t[j]；ﻩﻩ｝　　　　　　　　　／/模式串向右移动k＋＋;}ﻩcoｕｔ＜<"KMP匹配查找的时间复杂度为"<(iｎt）T[0]）reｔurni-T［0];　　　　　　　/／匹配成功ﻩelserｅtｕrn０;｝/／Ｉndｅx_ＫMPｖoidmaｉｎ(){ﻩSSｔｒiｎｇT，S；iｎｔｐ,i,ｊ,k1,k2;p＝1；ﻩcouｔ<<"请输入字符串匹配主串:"＜＜endｌ；ciｎ>>S；ﻩcouｔ<<"请输入字符串匹配模式串："<

8、j++)　｛ﻩT[0］=j;　}　　　　　　　／/存储字符串　ﻩcｏut<＜"普通算法:"＜

9、ｑqqqqｑqqqqｑqｑqｑqｑｑｑqqｖbn’;运行界面如下:小结：得到普通匹配算法的时间复杂度为４４0，而KMP算法的时间复杂度为66，显然在匹配算法中,ＫＭP算法优于普通算法,节省了时间以及资源。（２）当输入主串为S=’asdfｇｈjlｋlzxcｖbnmqｗertyｕiop’；模式串为T＝qwerｔｙui’运行结果如下：小结:当匹配串重复出现的字符不多时，ＫＭＰ算法的优势无法明显体现出来，ＫＭＰ的复杂度不一定比普通匹配的小。（3)还有一个问题就是当我匹配模式串只输入一个字符的话系统会出现问题普通算法的可以做但是KMP的就出错了。个人收集整理勿做商业用途(４)对于T（0)我是这样

10、理解的1./／生成一个其值等于串常量strs的串T2.voidSｔｒAssign（SSｔriｎg&Ｔ,ｃｈar　*strs)3.{4.iｎti；5.T[0]=0;/／0号单元存储字串长度6.for（i＝0;ｓtrs[i］;i+＋)　//用数组ｓtrs给串T赋值7.Ｔ［i+1］　=sｔrs［i]；8.T[0］　=　i；9.｝但是在上面的程序上我看书里面可以直接拿来用,就没有重新去对Ｔ进行赋值了。问题出现在ｇeｔ_next(）