模式匹配： 在字符串S中，子串P的定位操作通常稱做串的模式匹配。說白了，就是在一個字符串中尋找子串。在Suffix Trie和PAT tree中我們已經討論過匹配子串的方法了。這里我們討論一種線性匹配算法來尋找子串。
?
例： 我們要在S="ababcabcacbab"中查找子串P="abcac"。下圖左側是一種很普通的模式匹配算法
這種普通的模式匹配算法很簡單，但時間復雜度是O(n*m)。其中n=S.length，m=T.length.? 代價很高。難道真的要像第三趟到第四趟那樣：好不容易匹配到S中的第7個位置，但由于不相同，則有回溯到第4個位置重新開始。
?
其實，每一次匹配過后，主串S中被匹配過的位置其實不用再匹配了。也就是上一趟匹配結果對下一趟有指導作用。 我們用一個證明來說明這一點(假如主串S=s1 s2 .... sn ，模式串P=p1 p2 ... pm? )。
?
證明：當一趟匹配完成之后，我們發現si !=pj 。那么至少說明了模式串p1... p(j-1)是匹配成功的。也就是得到了：? p1? p2? ...? p(j-1) = s(i-j+1) ? s(i-j+2) .....? s(i-1) 。 比如第三趟 s7!=p5 => s2...s6=p1...p4 = "abca".
???????? 如果像上圖左側算法那樣，從第三趟i=7回溯到第四趟i=4是有必要的話，那么也說第四趟可能完全匹配到了模式串P。好，我們現在就假設si != sj之后，i 回溯主串(i-j+1)的下一個位置上可以匹配成功模式串P，那么我們可以得到 p1 p2 ... p(j-1) =s(i-j+2)?? s(i-j+3) ... s(i)。
???????? 合并下標藍色的兩個式子，我們可以得到：
?????????????????? s(i-j+1) ? s(i-j+2) .....? s(i-1)= s(i-j+2)?? s(i-j+3) ...? s(i)
???????? 也就是：? s(i-j+1)= s(i-j+2)= s(i-j+3)= .... =s(i-1)=s(i)
???????? 我靠，主串S中全部的字符都一樣，這種情況下才必須每一次都回到主串的下一個位置上重新開始。而只要有字符不同，就完全沒有這個必要了。好了，基于這個證明成果，我們開始介紹KMP算法。
?
?
KMP 模式匹配 —— D.E.Knuth?? V.R.Pratt和J.H.Morris同時發現的。因此人們稱它為克努特-莫里斯-莫拉特操作（簡稱KMP算法）。 KMP的優勢在于當每一趟匹配結果中出現了不等情況時，主串并不需要回溯位置i (上面已經證明)，而只要 回溯模式串P即可 。也就是說，只需要在主串S的位置i 處重新與模式串的位置k進行比較(如上圖右側過程)。 那么這個 重新 需要定位的模式串k位置有什么要求呢，或者說我們怎么確定這個k呢。我們再用一個小小的證明來揭示( 還是假如主串S=s1 s2 .... sn ，模式串P=p1 p2 ... pm? )：
?
證明：當一趟匹配完成之后，我們發現si !=pj 。此時首先可以肯定的是k< j，因為模式串j 必須回溯。
??????? 如果 s1 與 pk 有重新比較的必要，那么模式串P前k-1個字符必須滿足下列關系式：
??????????????????????????? p1? p2? ...? p(k-1)=s(i-k+1)? s(i-k+2) ...? s(i-1)
??????? 此外，由于經過額一趟的匹配之后，已經可以得到“部分匹配”結果，主串S中i 位置的前k個字符一定等于模式串P中j 位置上的前k個字符：
??????????? ? ? ? ? ?????? p(j-k+1)? p(j-k+2)? ...? p(j-1) = s(i-k+1) ? s(i-k+2) .....? s(i-1) 。
??????? 合并兩個藍色的式子：
?????????????????????????? p1? p2? ...? p(k-1) = p(j-k+1) ? p(j-k+2)?? ... ? p(j-1)
??????? 我們發現了，位置k的值取決于模式串P自己必須滿足上面這個紅色的式子。
?
?
失效函數： 當在模式串P的第j 個位置上發生匹配不成功時，需要將模式串回溯到位置 k處的這樣一個 f(j)=k 的函數，就叫做失效函數。其中j 和k 的值必須滿足 p1? p2? ...? p(k-1) = p(j-k+1) ? p(j-k+2)?? ... ? p(j-1)。 也就是說 pj 的前k-1個字符必須等于pk 的前k-1 個字符。因此，失效函數f(j)的定義如下：
?
???????????????????????????????????????????????? 0?????? 當j=1時
?????????????????????????????????? f(j) =????? Max{k|1<k<j 且 p1...p(k-1)=p(j-k+1)...p(j-1) }
???????????????????????????????????????????????? 1?????? 不滿足上面的情況
?
比如模式串P=“abcac”的每一個位置的失效函數如下：
??????????????????????????????????? ? ? ? ? j???????? 1 ? 2 ? 3?? 4?? 5
?????????????????????????????????????????? P???????? a?? b?? c?? a??? c
???????????????????????????????????????? k=f(j)???? 0?? 1?? 1?? 1?? 2
失效函數的算法
?? ? 假如f(j)=k，則表明 p1...p(k-1) = p(j-k+1)...p(j-1)。這說明 pj 的前k-1個字符必須等于pk 的前k-1 個字符。也就是說p1...pk一定是p1...pj的一個后綴子串。因此我們可以把模式串P與自身做KMP算法的匹配來求解這個K值。算法如下：
???? (1) 若 pk=pj, 則 p1...p(k-1)pk= p(j-k+1)...p(j-1) pj 。 表明f(j+1)=k+1
???? (2) 若 pk!=pj , 則可以把求f(j+1)看成以P為主串和匹配串的模式匹配問題。即 pk!=pj 則比較pj與p(f(k))，如果pj==p(f(k))，則f(j+1)=f(k)+1。否則繼續比較下去直到f(k)=0為止。
?
?? ?? 失效函數算法的運行時間是o(m).
?
?
KMP算法Java源代碼
package net.hr.algorithm.string;
public class KMP {
private int[] next=null;
private char[] mainAry=null;
private char[] patternAry=null;
public KMP(String main,String pattern){
this.mainAry=new char[main.length()+1];
this.patternAry=new char[pattern.length()+1];
System.arraycopy(main.toCharArray(),0,mainAry,1,main.length());
System.arraycopy(pattern.toCharArray(),0,patternAry,1,pattern.length());
this.next=new int[pattern.length()+1];
}
/**
* KMP匹配
* @param pos 從主串起始位置開始
*/
public int match(int pos){
if(pos>mainAry.length)
throw new IndexOutOfBoundsException();
failFunction();
int i=pos,j=1;
while(i<mainAry.length&&j<patternAry.length){
if(j==0||mainAry[i]==patternAry[j]){
++i;
++j;
}else{
j=next[j];
}
}
if(j>=patternAry.length) return i-patternAry.length+1;
else return 0;
}
/**
* 匹配串失效函數
*/
private void failFunction(){
int i=1,j=0;
next[1]=0;
while(i<patternAry.length-1){
if(j==0||patternAry[i]==patternAry[j]){
next[++i]=++j;
}else{
j=next[j];
}
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
KMP kmp=new KMP("acabaabaabcacaabc","abaabcac");
System.out.println(kmp.match(1));
}
}
?
KMP算法效率
?
????? 對于長度為n的文本串和長度為m的模式串進行模式匹配的運行時間為O(n+m) . 很顯然，因為文本串在KMP算法中并不需要回溯，因此與模式串的比較次數為O(n)。但模式串要建立失效函數，所付出的代價是O(m)。因此總體的時間復雜度是O(m+n)。實際中，m要遠小于n，因此近似可以認為KMP效率為O(n)。
????? 但是KMP算法有種最壞的情況，當模式串P="aaaaa"時，即每一個字符都一樣的時候。則失效函數為：
?????????????????????????????????? j ? ? 1 2 3 4 5
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P?? ? a a a a a
???????????????????????????????? f(j)? ? 0 1 2 3 4
????? 此時如果主串中的s[i]!=p[j]的時候，根據模式串P回溯j=f(j)的原則。s[i]需要從模式串P的最后一個字符一步一步回溯到第一個字符，每次都要比較一遍。這時的時間復雜度為O(m)。那么對于n個字符的S串而言，最差的時間復雜度就是O(n*m)了，退化成了蠻力匹配。
?
???? KMP和后綴樹都可以用來匹配子串。因此我們這里與后綴樹做一個比較，雖然后綴樹在查找的過程中只需要大概O(m)的時間復雜度。對長度n的文本串建立后綴樹最好的算法需要O(n)時間復雜度， 因此后綴樹大致也需要O(n+m) 。
?
?
?
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
