kmp模式匹配算法

1、KMP字符串模式匹配算法詳解2009090419:28個人覺得這篇文章是網(wǎng)上的介紹有關KMP算法更讓人容易理解的文章了，確實說得很“詳細”，耐心地把它看完肯定會有所收獲的～～，另外有關模式函數(shù)值next[i]確實有很多版本啊，在另外一些面向對象的算法描述書中也有失效函數(shù)f(j)的說法，其實是一個意思，即next[j]=f(j1)1，不過還是next[j]這種表示法好理解?。篕MPKMP字符串模式字符串模式匹配詳解匹配詳解KMP字符串模式

2、匹配通俗點說就是一種在一個字符串中定位另一個串的高效算法。簡單匹配算法的時間復雜度為O(mn)KMP匹配算法。可以證明它的時間復雜度為O(mn).。一.簡單匹配算法簡單匹配算法先來看一個簡單匹配算法的函數(shù)：intIndex_BF(S[]T[]intpos)若串S中從第pos(S的下標0≤posStrLength(S))個字符起存在和串T相同的子串，則稱匹配成功，返回第一個這樣的子串在串S中的下標，否則返回1inti=posj=0whil

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

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

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