解讀KMP演算法

前后斷斷續續搞了5個月，每次都以為自己懂了， 但是要寫的時候都不知從何下手，然后又是各種找博客，看帖子，所以這次試著用自己的語言寫一個博客，
首先，KMP演算法就是從一個模板字串（S） 中匹配目標字串（P），匹配的話，首先就是想到了暴力匹配，也就是用兩個下標表示在S的下標（si） 和 P的下標（pi), 然后進行回圈，如果s.chatAt(si)==p.chatAt(pi)就是si ++， pi++； 如果不相等的話，就需要把si = si - pi + 1, pi = 0; ，然后判斷 pi == p.length()
相等的話，就是匹配成功，可以回傳， 不相等就繼續， 下面貼一下代碼， 圖就不畫了，

   public int violenceMatch(String s, String p){
     int sLen = s.length(), pLen = p.length();
     int si = 0, pi = 0;
     while (si < sLen && pi < pLen) {
       if (s.charAt(si) == p.charAt(pi)) {
         si++;
         pi++;
       } else {
         si = si - pi + 1;
         pi = 0;
       }
     }
     if (pi == pLen) {
       return si - pi;
     } else {
       return  -1;
     }
   }

使用暴力匹配的缺點很明顯，就是每次失配（就是s.chatAt(si) != p.chatAt(pi）的時候，需要把 si 的位置 置為s.chatAt(si)==p.chatAt(pi)開始的點的下一位，這樣會出現很多重復無效的匹配，
KMP演算法就是把這些重復無效的匹配解決了，具體怎么解決，這個也是KMP演算法的精髓（next陣列的求解）， 關于next陣列的求解，我們稍后說，我們先體會一下 怎么使用KMP演算法來進行字串匹配（如果只想了解next陣列是怎么求出來的，可以跳過這部分）， 舉個例子，有模式串S: "CDABADABCABADABAB", 目標串P: "ABADABAB"用目標串推出的next陣列是{0,0,1,0,1,2,3,2}(后面會具體講怎么推出來的)，現在我們開始使用KMP演算法進行匹配，一開始是 si = 0， pi = 0，

我們可以看到這個位置不匹配的，然后因為當前pi == 0 所以直接si += 1 pi 不動 進行下一步 此時 si = 1，pi = 0

此時也是不匹配的， 然后重復上一步， 此時 si = 2, pi = 0

當si = 2， pi= 0的時候，s.chatAt(si) == p.chatAt(pi) ，所以此時 si += 1, pi += 1， 重復這樣匹配，我們發現在si = 8,pi=6的時候失配了，這是用就需要用到我們的next陣列了，
這里先簡單說next陣列的一樣，是當前下標所對應的最長公共前后綴，注意是最長，不是個數，是長度!!! 公共前后綴，都是基于當前下標來說的，舉個例子 ABA 這個next陣列是 {0 0 1} 對于0下標，沒有前后綴， 因為只有1個數， 對于1的下標，前綴是A， 后綴是B，A != B, 所以還是0， 對于2的下標，前綴有 A， AB，后綴有 BA，A，所以值為1 ，后面會有詳細的介紹，這里只要分辨出前綴和后綴就可以了，
回到正題， 我們當前位置是失配， 所以需要用到next陣列，那么這個next陣列在這里有什么用呢？ 我們試想一下，在當前下標失配， 說明我前面的都是可以匹配上的，我們的next陣列是保存了最長的公共前后綴，我們是不是可以把失配下標的前一個位置在next陣列中對應的最大公共前后綴值來作為目標串（P）移動的距離，因為我當前失配的下標的前一個下標有一定的匹配距離，然后這個下標所對應的前綴是不是可以省略比對，直接移動最長公共前后綴的距離， 這里pi = 6的時候失配， next[6 - 1] = 2， 也就是前綴AB （下標0、1）和 后綴AB（下標4、5），我們是不是可以省略AB的比較，直接從 ABAD的A開始繼續匹配，因為對于 pi = 6來說， pi = 4, pi=5都是和S串上可以匹配上，省略pi = 0， pi = 1的比較，直接從pi = 2開始和si= 8 繼續比對，所以下標變化是si = 8, pi = next[6 - 1]=2也就是下圖：

此時對于si = 8, pi= 2 仍然沒有匹配上，然后再次使用next陣列， next[2 - 1] = 0，所以有 si = 8, pi = next[2 - 1] = 0

此時還是沒有匹配上，但是pi = 0， 所以 si+=1，此時 si = 9, pi = 0

后面下去都是匹配上了，所以可以回傳下標，
可能看到這里，你還是疑惑這個next下標為什么要這樣用呢？這里總結一下，然后就解釋next陣列的推導程序， 我們在 失配的時候，就需要移動目標串，問題是移動多少呢？不同于暴力匹配的做法，將 si和pi都一起移動，而是只移動 pi，這個移動的距離，和next陣列有關，我們當前失配的位置的前一個位置是可以和S模式串失配前的位置是可以匹配的，所以我們只要移動當前pi的前一個位置的最大公共前后綴距離，然后原本由后綴匹配的字符給前綴匹配（因為知道了最大公共前后綴的距離，所以這部分只是移動而已，不需要再重新的匹配），然后在失配的地方繼續進行新的比對，
這里開始講解一下next的推導，我們在前面提到過，next陣列對于當前下標所對應的最長公共前后綴，所以我們從index = 1 開始，因為 0 下標只有1個字符，沒有前后綴

對于下標1，我們可以很清楚的看到， 前綴是A， 后綴是B，A != B, 所以next[index] = 0，對下標index = 2進行查看

對于下標2，我們也可以很清楚的看到，前綴是A、AB，后綴是BA,A，只有A == A，所以next[index] = 1,好像到這里還是很簡單，我們可以先推出一個公式，p.chatAt(index) == p.chatAt(next[index - 1]) 成立的話 next[index] = next[index - 1] + 1, 不成立的話 next[index] = 0,后面我們就用這個公式進行求解，看下這個公式是否成立，在驗證結果之前，我先說一下為什么會得出這樣的公式， next陣列是保存了最長公共前后綴，這個概念說過很多次了，因為它特別重要， 我們對于當前下標，要想找到最長的公共前后綴，最好的辦法就是在前一個下標的最長公共前后綴的基礎上+1，這點沒有問題吧，所以就有了 p.chatAt(index) == p.chatAt(next[index - 1])， 那么接下來，我們就來驗證一下這個公式的正確性了，對于下標 index = 3，

有p.chatAt(3) != p.chatAt(next[3 - 1])所以next[3] = 0，我們也可以看出next[3]確實是0， 繼續 index = 4

在index = 4的時候，有 p.chatAt(4) == p.chatAt(next[4 - 1]) 所以next[4] = next[4 - 1] + 1，確實沒錯，繼續index = 5

在next = 5的時候，有p.chatAt(5) == p.chatAt(next[5 - 1]) 所以next[5] = next[5 - 1] + 1,也沒有錯誤 ，繼續 index = 6

在next =6 的時候， 有p.chatAt(6) == p.chatAt(next[6 - 1]), 所以next[6] = next[6 - 1] + 1, 也沒有錯誤，繼續 index = 7

在next = 7 的時候， 有p.chatAt(7) != p.chatAt(next[7 - 1]), 按照公式，此時的next[7] 應該是0 才對呀，但是我寫的是 2，我們可以看一下，確實也是2 因為前綴 AB 和后綴AB相等，所以是2， 但是這是為什么呢？我們可以知道 p.chatAt(7) 確實是不等于 p.chatAt(next[7 - 1])，但是不要忘記，我們的next保存的是最長公共前后綴，next[7 - 1] = 3，說明下標0 、 1、 2和下標4、5、6是一一對應的，所以我們對下標4 和7進行比較，發現不相等，按照一開始的思路，我們會把next[7]設為0， 但是我們可以看一下下標 0、 1、 2 、 3這里，對于下標3 是我們下標7要比較的，但是看一下下標2的位置在next陣列是1，這表明了，對于下標2，的最長公共前后綴是1，在求next[3]的時候，我們用p.chatAt(3) 和p.chatAt(next[3 - 1])進行比較，對于現在的下標7， 我們是不是可以把它當成是下標3 呢？ 完全可以，因為下標0、1、2和下標4、5、6一一對應， 下標3 和7 沒有匹配上，就可以把下標7 看成是下標3， 此時應該是用 p.chatAt(7) 和 p.chatAt(next[3 - 1]), 對于為什么前面是7 后面是next[3- 1] 而不是next[7 - 1]的，如果用next[7 - 1]了， 是不是就陷入了死回圈了？ 其實這里也就是把3的下標當作是7來看待，對于3前面的沒有其他影響，所以才是這樣的， 那么到了此時，我們可以很清晰的求出next陣列，然后結合前面的講解， 就是一個完整的KMP了，
第一次寫博客寫了2000+字，花費了一些心血畫圖，試圖用最簡單的話來敘述這個演算法，但是好像沒有做到，有一些東西在我這個層次還沒有看到，所以也沒有用到最簡單的話來敘述完全部，大家能多看幾遍，也是可以理解這個演算法的精妙之處，最后貼一下完整代碼：

package com.hl.solution;


/**
 * @author Hl
 * @create 2021/3/3 0:18
 */
public class KMP {

    public static void main(String[] args) {
        KMP kmp = new KMP();
        String s = "BBC ABCDAB ABCDABCDABDE";
        String p = "12";
        int i = kmp.kmpMatch(s, p);
        int j = kmp.violenceMatch(s, p);
        System.out.println("KMP演算法結果： "+i);
        System.out.println("暴力匹配結果： " + j);

    }
	
  // KMP匹配
    public int kmpMatch(String s, String p){
        int[] next = getNext(p);
        int sLen = s.length(), pLen = p.length();
        int sl = 0, pl = 0;
        while (sl < sLen) {
            if (s.charAt(sl) == p.charAt(pl)) {
                sl++;
                pl++;
            } else if (pl == 0) sl++;
            else pl = next[pl - 1];
            if (pl == pLen) {
                return sl - pl;
            }
        }
        return -1;
    }

  // 求next陣列
    public int[] getNext(String p){
        int[] next = new int[p.length()];
        for (int i = 1; i < p.length(); i++) {
            int index = next[i - 1];
            while (index > 0 && p.charAt(i) != p.charAt(index)) {
                index = next[index - 1];
            }
            if (p.charAt(i) == p.charAt(index)) {
                next[i] = index + 1;
            }
        }
        return next;
    }

  // 暴力匹配
    public int violenceMatch(String s, String p){
        int sLen = s.length(), pLen = p.length();
        int si = 0, pi = 0;
        while (si < sLen && pi < pLen) {
            if (s.charAt(si) == p.charAt(pi)) {
                si++;
                pi++;
            } else {
                si = si - pi + 1;
                pi = 0;
            }
        }
        if (pi == pLen) {
            return si - pi;
        } else {
            return  -1;
        }
    }
}

希望大家都能在我這里得到一些識訓，感謝看了這么久........

標籤：其他

上一篇：Ardupilot的Copter的throttle_loop

下一篇：python繪制高顏值房價與地鐵線路分布圖