Java數據結構之KMP算法詳解以及代碼實現

我們此前學瞭前綴樹Trie的實現原理以及Java代碼的實現。Trie樹很好，但是它隻能基於前綴匹配實現功能。但是如果我們的需求是：一個已知字符串中查找子串，並且子串並不一定符合前綴匹配，那麼此時Trie樹就無能為力瞭。

實際上這種字符串匹配的需求，在開發中非常常見，例如判斷一個字符串是否包括某些子串，然後進行分別的處理。

暴力匹配算法（Brute-Force，BF）

這是最常見的算法字符串匹配算法，暴力匹配也叫樸素匹配。

思路很簡單，從主串的第i個字符開始遍歷，依次與子串的每個字符進行匹配，如果某個字符匹配失敗，則主串回溯第i+1個字符，子串回溯到第1個字符，重新開始匹配，直到遍歷完主串匹配失敗或者遍歷完子串匹配成功。

很明顯這種算法需要在一個雙重for循環中實現，時間復雜度為O(m*n)，m為主串長度，n為子串長度。隨著字符串長度的增長，時間復雜度快速上升。

Java中字符串的contains方法實際上就是采用的BF算法。

public static int bf(String word, String k) {
    char[] wordChars = word.toCharArray();
    char[] keyChars = k.toCharArray();
    for (int i = 0; i < wordChars.length; i++) {
        int j = 0, x = i;
        //依次匹配
        while (x < wordChars.length && j < keyChars.length && wordChars[x] == keyChars[j]) {
            x++;
            j++;
        }
        if (j == keyChars.length) {
            return i;
        }
    }
    return -1;
}

概念和原理

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 於1977年共同提出的，稱之為 Knuth-Morria-Pratt 算法，簡稱 KMP 算法。

KMP算法是一種改進的字符串匹配算法，核心是利用之前的匹配失敗時留下的信息，選擇最長匹配長度直接滑動，從而減少匹配次數。KMP 算法時間復雜度為O(m+n)，m為主串長度，n為子串長度。

BF匹配失敗之後，主串和子串都會最大回溯，但是很多時候都是沒有必要的。例如對於主串abababcd，子串ababc，第一次匹配之後，很明顯主串和子串會匹配失敗，但是我們能夠知道他們的能夠匹配的前綴串，即abab：

如果在第二次匹配的時候，主串不回溯，子串滑動兩個字符長度，那麼我們就能在第二次的時候實現匹配成功。

到這裡，這種加速的方法已經呼之欲出瞭，但是我們先介紹兩個重要概念：

1.匹配前綴：在某一次主串和子串的匹配失敗之後，前面匹配成功的那部分子串就被稱為匹配前綴。這就是一次匹配失敗時留下的信息。

例如主串abcde，子串abcc，那麼在第一次匹配的時候，匹配前綴為abc。

2.最長匹配長度：對於每次匹配失敗後的匹配前綴串，其前綴子串（連續，且一定包括第一個字符，不包括最後一個字符）和後綴子串（連續，且一定包括最後一個字符，不包括第一個字符）中，相同的前後綴子串的最長子串長度，此時的前綴、後綴字串也被稱為最長真前綴、後綴子串。

• 例如匹配前綴abc，沒有匹配的前綴和後綴，那麼其最長匹配長度為0。
• 例如匹配前綴cbcbc，最長匹配的前綴和後綴子串為cbc，那麼其最長匹配長度為3。
• 例如匹配前綴abbcbab，最長匹配的前綴和後綴子串為ab，那麼其最長匹配長度為2。

有瞭這兩個概念，那麼我們才能進行跳躍式滑動，對於主串，在匹配失敗的位置不進行回溯，對於子串，則是回溯（滑動）到其匹配前綴的最長匹配長度的位置上繼續匹配，這樣就跳過瞭之前的部字符串的匹配，且隻需要匹配剩下的部分字符串即可。

我們再詳細解釋下，這裡子串跳過的到底什麼？實際上它跳過的就是匹配前綴串的最長匹配長度串。
設主串abababcd，子串ababc，第一次匹配失敗之後，主串匹配索引i=4，子串匹配索引j=4，此時匹配的相同前綴串為abab，它的最長匹配長度為2，即最長前綴串ab和最長後綴串ab。

那麼第二次匹配之前，字串匹配索引j直接跳到第一匹配的相同前綴串的最長匹配長度的索引位置上即j=2。我們可以這麼理解，主串的第一次匹配的相同前綴串的最長匹配後綴，與子串第一次匹配的相同前綴串的最長匹配前綴相等（或者說重合）。這是我們在底層一次失敗匹配之後得到的有效信息，在第二次匹配時自然可以利用起來，利用最長的前後綴匹配信息，跳過這些多餘的匹配，實現加速。（後續學習的AC自動機也是采用瞭前後綴匹配的思想）

這就是KMP算法加速的核心原理，每次匹配失敗之後，利用匹配失敗的信息，找到最長匹配長度，然後主串不回溯，子串盡可能少的回溯，相比於BF算法，減少瞭沒必要的匹配次數。

next數組

基於上面的原理，我們知道可能會不止一次查找最長匹配長度，而且我們會發現，最長匹配長度的范圍隻能在子串長度范圍之內，而且其計算結果隻和子串有關。那麼我們就可以先初始化一個數組，用來保存不同長度的前綴的最長匹配長度。

這就是所謂的next數組，也被稱為部分匹配表(Partial Match Table)，也是KMP算法的核心。next數組的大小就是子串的長度，每個的索引位置i表示長度為i+1的子串的匹配前綴子串，值v表示對應匹配前綴子串的最長匹配長度。

假設子串為ababc，那麼next數組值為：

假設子串為abcabdabcabc，那麼對應的next數組如下：

其實很好理解：

現在，我們的首要問題變成瞭求next數組。

首先，切next數組的問題實際上就是求最大的前、後綴長度的問題，那麼我們可以使用最樸素的方式求解：

public static int[] getNext(String word) {
    int[] next = new int[word.length()];
    //從兩個字符的子串開始遍歷
    for (int i = 1; i < word.length(); i++) {
        int k = i;
        //從最大的最長匹配值開始縮短
        while (k > 0) {
            //如果前綴等於後綴，那麼表示獲取到瞭最長匹配，直接返回
            if (word.substring(0, k).equals(word.substring(i - (k - 1), i + 1))) {
                next[i] = k;
                break;
            }
            k--;
        }
    }
    return next;
}

不難發現，求解next數組的時間復雜度為O(n^2)，是否有更快速的方法呢？當然有，可以發現，在求next[i]的最長匹配長度的時候，next[0], next[1], … next[i-1]的結果已經求出來瞭。因此我們嘗試利用此前的結果直接推導出後面的結果。下面是分情況討論。

設子串為str=ababc，i=3，那麼next[i-1]=1，即子串aba的的最長匹配長度為1，那麼str[next[i-1]]實際上就是最長匹配子串前綴後一個字符，即str[1]=b。

如果str[i]=str[next[i-1]]，就相當於在前一個子串的最長匹配長度的基礎上增加瞭一位，即next[i]=next[i-1]+1。如下圖：

如果str[i]!=str[next[i-1]]，此時就會復雜一些。此時我們需要縮短最長匹配子串的長度，具體怎麼縮短呢？

設str = abcabdabcabc，設i = 11，即最後一個字符c，那麼next[i-1] = 5，但是由於str[i] != str[next[i-1]]，即d != c，那麼此時我們需要求i-1的最長匹配長度子串abcab的最長匹配長度子串，即next[next[i-1]-1] = 2，然後判斷str[i]是否等於str[next[next[i-1]-1]]，如果相等則同第一種情況，否則繼續縮減直到next[next[i-1]-1]為0為止，此時表示當前子串的最長匹配長度也為0。如下圖：

基於上面的規律，我們的改進算法如下：

public static int[] getNext2(String k) {
    int[] next = new int[k.length()];
    char[] chars = k.toCharArray();
    //i表示匹配的字符索引，pre表示前一個子串的最長匹配長度，即next[i-1]
    int i = 1, pre = next[i - 1];
    while (i < k.length()) {
        //如果新增的字符與前一個子串的最長匹配子串前綴的後一個字符相等
        if (chars[i] == chars[pre]) {
            //next[i]=next[i-1]+1
            pre++;
            next[i] = pre;
            //繼續後移
            i++;
        }
        //如果不相等，且前一個子串的最長匹配長度不為0
        //那麼求i-1的最長匹配長度子串的最長匹配長度子串，即pre=next[next[i-1]-1]
        //然後在下一輪循環中繼續比較chars[i] == chars[pre]，此時i並沒有自增
        else if (pre != 0) {
            //next[next[i-1]-1]
            pre = next[pre - 1];
        }
        //如果不相等，且前一個子串的最長匹配長度為0，那麼說明當前子串的最長匹配長度也為0
        else {
            //當前子串的最長匹配長度為0
            next[i] = 0;
            //繼續後移
            i++;
        }
    }
    return next;

這種算法的時間復雜度為O(n)，大大縮短瞭求next數組的時間。

KMP匹配

有瞭next數組，那麼KMP算法就很容易實現瞭。

使用i和j分別表示主串和子串的匹配進度，i永遠不會回退，依次匹配主串和子串的字符：

1.如果字符相等則推進i、j，並且判斷如果匹配到瞭一個完整的子串，那麼返回起始索引。

2.如果不相等：

• 如果當前子串進度為0，那麼子串不需要回退，主串向後推進i，重新開始匹配；
• 如果當前子串進度不為0，那麼子串進度需要回退到next[j-1]的位置，此前的位置不再需要匹配，主串不需要向後推進i，隨後重新開始匹配。

如果i進度匹配完畢，那麼退出循環，表示沒有匹配到任何完整的子串，返回-1。

public static int kmp(String word, String k) {
    int[] next = getNext(k);
    //i,j分別表示主串和子串的匹配進度
    int m = word.length(), n = k.length(), i = 0, j = 0;
    //如果i匹配完畢，那麼退出循環
    while (i < m) {
        //如果字符相等，那麼向後推進i、j
        if (word.charAt(i) == k.charAt(j)) {
            i++;
            j++;
            //如果匹配到瞭一個完整的子串
            if (j == n) {
                //返回起始索引
                return i - n;
            }
        }
        //如果當前子串進度為0，那麼子串不需要回退，主串向後推進i
        else if (j == 0) {
            i++;
        }
        //如果當前子串進度不為0，那麼子串需要回退，主串不需要向後推進i
        else {
            //子串進度j回退
            j = next[j - 1];
        }
    }
    return -1;
}

KMP全匹配

上面我們的實現是返回第一個匹配到的模式串的起始索引，那麼如果我們需要返回所有匹配到的模式串的起始索引呢？
其實也很簡單。在每次匹配某個字符成功之後判斷，如果匹配到瞭一個完整的子串，那麼我們求起始索引並且加入結果集，然後子串點位j需要回退，繼續循環。

public static List<Integer> kmpAll(String word, String k) {
    List<Integer> res = new ArrayList<>();
    int[] next = getNext(k);
    //i,j分別表示主串和子串的匹配進度
    int m = word.length(), n = k.length(), i = 0, j = 0;
    //如果i匹配完畢，或者j匹配完畢，那麼退出循環
    while (i < m) {
        //如果字符相等，那麼向後推進i、j
        if (word.charAt(i) == k.charAt(j)) {
            i++;
            j++;
            //如果匹配到瞭一個完整的子串
            if (j == n) {
                //將起始索引加入結果集
                res.add(i - n);
                //子串進度j回退
                j = next[j - 1];
            }
        }
        //如果當前子串進度為0，那麼子串不需要回退，主串向後推進i
        else if (j == 0) {
            i++;
        }
        //如果當前子串進度不為0，那麼子串需要回退，主串不需要向後推進i
        else {
            //子串進度j回退
            j = next[j - 1];
        }
    }
    return res;
}

總結

KMP算法是一種優化的字符串匹配算法，m為主串長度，n為子串長度。由於構建瞭 next 數組，空間復雜度為 O(m)。匹配時主串不會回退，子串回退不會超過n，總體算法時間復雜度為O(m+n)。

next數組是實現算法加速的關鍵，它的核心是查找最長前後綴匹配長度，這也是理解KMP算法的核心。

到此這篇關於Java數據結構之KMP算法詳解以及代碼實現的文章就介紹到這瞭,更多相關Java KMP算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

• Java數據結構之AC自動機算法的實現
• JAVA多種方法實現字符串反轉
• 詳解Java中字典樹(Trie樹)的圖解與實現
• 詳解Java中AC自動機的原理與實現
• Java基礎入門語法–String類