詳解Java中KMP算法的圖解與實現

Posted on by

圖解

kmp算法跟之前講的bm算法思想有一定的相似性。之前提到過，bm算法中有個好後綴的概念，而在kmp中有個好前綴的概念，什麼是好前綴，我們先來看下面這個例子。

觀察上面這個例子，已經匹配的abcde稱為好前綴，a與之後的bcde都不匹配，所以沒有必要再比一次，直接滑動到e之後即可。

那如果好前綴中有互相匹配的字符呢？

觀察上面這個例子，這個時候如果我們直接滑到好前綴之後，則會過度滑動，錯失匹配子串。那我們如何根據好前綴來進行合理滑動？

其實就是看當前的好前綴的前綴和後綴是否有匹配的，找到最長匹配長度，直接滑動。鑒於不止一次找最長匹配長度，我們完全可以先初始化一個數組，保存在當前好前綴情況下，最長匹配長度是多少，這時候我們的next數組就出來瞭。

我們定義一個next數組，表示在當前好前綴下，好前綴的前綴和後綴的最長匹配子串長度，這個最長匹配長度表示這個子串之前已經匹配過匹配瞭，不需要再次進行匹配，直接從子串的下一個字符開始匹配。

我們是否每次算next[i]時都需要每一個字符進行匹配，是否可以根據next[i – 1]進行推導以便減少不必要的比較。

帶著這個思路我們來看看下面的步驟：

假設next[i – 1] = k – 1;

如果modelStr[k] = modelStr[i] 則next[i]=k

如果modelStr[k] != modelStr[i]，我們是否可以直接認定next[i] = next[i – 1]？

通過上面這個例子，我們可以很清晰的看到，next[i]!=next[i-1]，那當modelStr[k]!=modelStr[i]時候，我們已知next[0],next[1]…next[i-1]，如何推倒出next[i]呢？

假設modelStr[x…i]是前綴後綴能匹配的最長後綴子串，那麼最長匹配前綴子串為modelStr[0…i-x]

我們在求這個最長匹配串的時候，他的前面的次長匹配串（不包含當前i的），也就是modelStr[x…i-1]在之前應該是已經求解出來瞭的，因此我們隻需要找到這個某一個已經求解的匹配串，假設前綴子串為modelStr[0…i-x-1],後綴子串為modelStr[x…i-1],且modelStr[i-x] == modelStr[i],這個前綴後綴子串即為次前綴子串，加上當前字符即為最長匹配前綴後綴子串。

代碼實現

首先在kmp算法中最主要的next數組，這個數組標志著截止到當前下標的最長前綴後綴匹配子串字符個數，kmp算法裡面，如果某個前綴是好前綴，即與模式串前綴匹配，我們就可以利用一定的技巧不止向前滑動一個字符，具體看前面的講解。我們提前不知道哪些是好前綴，並且匹配過程不止一次，因此我們在最開始調用一個初始化方法，初始化next數組。

1.如果上一個字符的最長前綴子串的下一個字符==當前字符，上一個字符的最長前綴子串直接加上當前字符即可

2.如果不等於，需要找到之前存在的最長前綴子串的下一個字符等於當前子串的，然後設置當前字符子串的最長前綴後綴子串

int[] next ;
    /**
     * 初始化next數組
     * @param modelStr
     */
    public void init(char[] modelStr) {
        //首先計算next數組
        //遍歷modelStr，遍歷到的字符與之前字符組成一個串
        next = new int[modelStr.length];
        int start = 0;
        while (start < modelStr.length) {
            next[start] = this.recursion(start, modelStr);
            ++ start;
        }
    }

    /**
     *
     * @param i 當前遍歷到的字符
     * @return
     */
    private int recursion(int i, char[] modelStr) {
        //next記錄的是個數，不是下標
        if (0 == i) {
            return 0;
        }
        int last = next[i -1];
        //沒有匹配的,直接判斷第一個是否匹配
        if (0 == last) {
            if (modelStr[last] == modelStr[i]) {
                return 1;
            }
            return 0;
        }
        //如果last不為0，有值，可以作為最長匹配的前綴
        if (modelStr[last] == modelStr[i]) {
            return next[i - 1] + 1;
        }
        //當next[i-1]對應的子串的下一個值與modelStr不匹配時，需要找到當前要找的最長匹配子串的次長子串
        //依據就是次長子串對應的子串的下一個字符==modelStr[i];
        int tempIndex = i;
        while (tempIndex > 0) {
            last = next[tempIndex - 1];
            //找到第一個下一個字符是當前字符的匹配子串
            if (modelStr[last] == modelStr[i]) {
                return last + 1;
            }
            -- tempIndex;
        }
        return 0;
    }

然後開始利用next數組進行匹配，從第一個字符開始匹配進行匹配，找到第一個不匹配的字符，這時候之前的都是匹配的，接下來先判斷是否已經是完全匹配，是直接返回，不是，判斷是否第一個就不匹配，是直接往後面匹配。如果有好前綴，這時候就利用到瞭next數組，通過next數組知道當前可以從哪個開始匹配，之前的都不用進行匹配。

public int kmp(char[] mainStr, char[] modelStr) {
        //開始進行匹配
        int i = 0, j = 0;
        while (i + modelStr.length <= mainStr.length) {
            while (j < modelStr.length) {
                //找到第一個不匹配的位置
                if (modelStr[j] != mainStr[i]) {
                    break;
                }
                ++ i;
                ++ j;
            }
            if (j == modelStr.length) {
                //證明完全匹配
                return i - j;
            }
            //走到這裡找到的是第一個不匹配的位置
            if (j == 0) {
                ++ i;
                continue;
            }
            //從好前綴後一個匹配
            j = next[j - 1];
        }
        return -1;
    }

到此這篇關於詳解Java中KMP算法的圖解與實現的文章就介紹到這瞭,更多相關Java KMP算法內容請搜索LevelAH以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持LevelAH！

推薦閱讀：