KMP算法介紹總結

KMP算法來源

KMP算法英文是（Knuth-Morris-Pratt），它是以三個發明者命名的，起頭的K代表的是著名科學家Donald Knuth.其最常用于字元串比對，查詢。

算法說明

一般我們比對字元串的時候，我們從目标字元串dstr(假設長度為n)的第一個下标選取和sptr長度（長度為m）一樣的子字元串進行比較，如果一樣，就傳回開始處的下标值，不一樣，選取str下一個下标，同樣選取長度為n的字元串進行比較，直到str的末尾（實際比較時，下标移動到n-m）.這樣的時間複雜度是O(m*n)。而使用KMP算法的複雜度是O(m+n)。

那KMP是如何簡化時間複雜度的了？利用目标字元串dstr的性質（比如裡面部分字元串的重複性，即使不存在重複字段，在比較時，實作最大的移動量）。舉例說明：有一個字元串“BBC ABCDAB ABCDABCDABDE”,想知道，裡面是否包含字元串""ABCDABD"?

1. 看上圖所示：字元串“BBC ABCDAB ABCDABCDABDE”的第一個字元與搜尋詞"ABCDABD"的第一個字元，進行比較，因為B與A不比對，是以搜尋詞後移一位。
2. 往後移動一位以後，還是不一緻，繼續移動。知道第一位相同 ，此時情況如下所示：

   

3. 第一個字元的數字相同後，繼續比較第2個字元，也完全相同

   

   直到有一個字元不完全相同：

   

   D對應的是空格。此時正常的做法就是将搜尋詞整個後移一位，然後再依次進行比較。但是這樣做，因為你需要從第2位開始，依次進行比較，那些曾經比過的位。但此時的實際情況卻是：當D與空格不相比對的時候，你實際上是知道簽名六個字元是“ABCDAB”的。KMP算法就是利用了這個資訊，不把搜尋的起始位置移動到已經比較過的位置，繼續把他向後移動，避免了來回移動，進而提高效率，但這樣，假如剛好有一個子串從第2位開始能比對上不是就遺漏了嗎？
4. KMP 當然不是随意的移動，是有一定規則的。這個規則就是《部分比對表》或者也稱之為Next表。這是目前例子的Next表：

   

5. 我們先暫時不管，這種表是如何産生的和為什麼，先按照這張表進行位移。當我們發現空格與D不比對，前面6個字元“ABCDAB”是比對的時候。查表可值，最後一個比對字元B對應的“部分比對值”是2，按照下面的公式計算向後移動的位數：

移動位數 = 已比對的字元數-對應的部分比對值
           

從上面的公式我們可以得出：6-2=4，是以将搜尋詞向後移動4位，到達下面的位置。

1. 移動了4位以後，再次依次比較，發現空格與C不比對，此時，已比對的字元數為2（“AB”）,對應的“部分比對值”為0，是以移動位數為2，于是往後再移動2位。

   

2. 空格與A不比對。直接後移動一位。

   

   ，此時C與D不比對。比對的字元數為6，部分比對值為2，6-2=4，移動4位。

   

3. 此時發現完全比對了。此時如果還要繼續找出所有的比對值，則7-0=7，移動7位繼續往下即可。
4. 從上面可以看出KMP算法非常重要的點就是得出Next表。

   

   這裡先介紹“字首”和“字尾”。“字首”指除了最後一個字元以外，一個字元串的全部頭部組合；“字尾”指除了第一個字元以外，一個字元串的全部尾部組合。

   “部分比對值就是”字首“和”字尾“的最長的共有元素的長度。

• "A"的字首和字尾都為空集，共有元素的長度為0；
• "AB"的字首為[A]，字尾為[B]，共有元素的長度為0；
• "ABC"的字首為[A, AB]，字尾為[BC, C]，共有元素的長度0；
• "ABCD"的字首為[A, AB, ABC]，字尾為[BCD, CD, D]，共有元素的長度為0；
• "ABCDA"的字首為[A, AB, ABC, ABCD]，字尾為[BCDA, CDA, DA, A]，共有元素為"A"，長度為1；
• "ABCDAB"的字首為[A, AB, ABC, ABCD, ABCDA]，字尾為[BCDAB, CDAB, DAB, AB, B]，共有元素為"AB"，長度為2；

• "ABCDABD"的字首為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，字尾為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0

  以上就是Next表的計算方法。其實，"部分比對"的實質是，有時候，字元串頭部和尾部會有重複。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分比對值"就是2（"AB"的長度）。搜尋詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分比對值），就可以來到第二個"AB"的位置。

參考文檔：http://www.cnblogs.com/c-cloud/p/3224788.html

http://blog.csdn.net/starstar1992/article/details/54913261

轉載于:https://www.cnblogs.com/angellst/p/7778381.html