kmp模式匹配算法

1、KMP字符串模式匹配算法詳解2009090419:28個(gè)人覺(jué)得這篇文章是網(wǎng)上的介紹有關(guān)KMP算法更讓人容易理解的文章了，確實(shí)說(shuō)得很“詳細(xì)”，耐心地把它看完肯定會(huì)有所收獲的～～，另外有關(guān)模式函數(shù)值next[i]確實(shí)有很多版本啊，在另外一些面向?qū)ο蟮乃惴枋鰰?shū)中也有失效函數(shù)f(j)的說(shuō)法，其實(shí)是一個(gè)意思，即next[j]=f(j1)1，不過(guò)還是next[j]這種表示法好理解啊：KMPKMP字符串模式字符串模式匹配詳解匹配詳解KMP字符串模式

2、匹配通俗點(diǎn)說(shuō)就是一種在一個(gè)字符串中定位另一個(gè)串的高效算法。簡(jiǎn)單匹配算法的時(shí)間復(fù)雜度為O(mn)KMP匹配算法?？梢宰C明它的時(shí)間復(fù)雜度為O(mn).。一.簡(jiǎn)單匹配算法簡(jiǎn)單匹配算法先來(lái)看一個(gè)簡(jiǎn)單匹配算法的函數(shù)：intIndex_BF(S[]T[]intpos)若串S中從第pos(S的下標(biāo)0≤posStrLength(S))個(gè)字符起存在和串T相同的子串，則稱匹配成功，返回第一個(gè)這樣的子串在串S中的下標(biāo)，否則返回1inti=posj=0whil

3、e(S[ij]!=0繼續(xù)比較后一字符elseij=0重新開(kāi)始新的一輪匹配if(T[j]==0)returni匹配成功返回下標(biāo)elsereturn1串S中(第pos個(gè)字符起)不存在和串T相同的子串Index_BF此算法的思想是直截了當(dāng)?shù)模簩⒅鞔甋中某個(gè)位置i起始的子串和模式串T又一次發(fā)生了失配，所以T下標(biāo)又回溯到開(kāi)始，S下標(biāo)增1然后再次比較。這次T中的所有字符都和S中相應(yīng)的字符匹配了。函數(shù)返回T在S中的起始下標(biāo)3。如圖：二.KMPKMP匹

4、配算法匹配算法還是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，當(dāng)?shù)谝淮嗡阉鞯絊[5]和T[5]不等后，S下標(biāo)不是回溯到1，T下標(biāo)也不是回溯到開(kāi)始，而是根據(jù)T中T[5]==’d’的模式函數(shù)值（next[5]=2，為什么？后面講），直接比較S[5]和T[2]是否相等，因?yàn)橄嗟龋琒和T的下標(biāo)同時(shí)增加因?yàn)橛窒嗟?，S和T的下標(biāo)又同時(shí)增加。。。最終在S中找到了T。如圖：KMP匹配算法和簡(jiǎn)單匹配

5、算法效率比較，一個(gè)極端的例子是：在S=“AAAAAA…AAB“(100個(gè)A)中查找T=”AAAAAAAAAB”簡(jiǎn)單匹配算法每次都是比較到T的結(jié)尾，發(fā)現(xiàn)字符不同，然后T的下標(biāo)回溯到開(kāi)始，S的下標(biāo)也要回溯相同長(zhǎng)度后增1，繼續(xù)比較。如果使用KMP匹配算法，就不必回溯.對(duì)于一般文稿中串的匹配，簡(jiǎn)單匹配算法的時(shí)間復(fù)雜度可降為O(mn)，因此在多數(shù)的實(shí)際應(yīng)用場(chǎng)合下被應(yīng)用。KMP算法的核心思想是利用已經(jīng)得到的部分匹配信息來(lái)進(jìn)行后面的匹配過(guò)程?？辞懊娴?/p>