圖解

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

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

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

觀察上面這個(gè)例子，這個(gè)時(shí)候如果我們直接滑到好前綴之后，則會(huì)過度滑動(dòng)，錯(cuò)失匹配子串。那我們?nèi)绾胃鶕?jù)好前綴來進(jìn)行合理滑動(dòng)？

其實(shí)就是看當(dāng)前的好前綴的前綴和后綴是否有匹配的，找到最長(zhǎng)匹配長(zhǎng)度，直接滑動(dòng)。鑒于不止一次找最長(zhǎng)匹配長(zhǎng)度，我們完全可以先初始化一個(gè)數(shù)組，保存在當(dāng)前好前綴情況下，最長(zhǎng)匹配長(zhǎng)度是多少，這時(shí)候我們的next數(shù)組就出來了。

我們定義一個(gè)next數(shù)組，表示在當(dāng)前好前綴下，好前綴的前綴和后綴的最長(zhǎng)匹配子串長(zhǎng)度，這個(gè)最長(zhǎng)匹配長(zhǎng)度表示這個(gè)子串之前已經(jīng)匹配過匹配了，不需要再次進(jìn)行匹配，直接從子串的下一個(gè)字符開始匹配。

我們是否每次算next[i]時(shí)都需要每一個(gè)字符進(jìn)行匹配，是否可以根據(jù)next[i - 1]進(jìn)行推導(dǎo)以便減少不必要的比較。

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

假設(shè)next[i - 1] = k - 1;

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

如果modelStr[k] != modelStr[i]，我們是否可以直接認(rèn)定next[i] = next[i - 1]？

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

假設(shè)modelStr[x…i]是前綴后綴能匹配的最長(zhǎng)后綴子串，那么最長(zhǎng)匹配前綴子串為modelStr[0…i-x]

我們?cè)谇筮@個(gè)最長(zhǎng)匹配串的時(shí)候，他的前面的次長(zhǎng)匹配串（不包含當(dāng)前i的），也就是modelStr[x…i-1]在之前應(yīng)該是已經(jīng)求解出來了的，因此我們只需要找到這個(gè)某一個(gè)已經(jīng)求解的匹配串，假設(shè)前綴子串為modelStr[0…i-x-1],后綴子串為modelStr[x…i-1],且modelStr[i-x] == modelStr[i],這個(gè)前綴后綴子串即為次前綴子串，加上當(dāng)前字符即為最長(zhǎng)匹配前綴后綴子串。

代碼實(shí)現(xiàn)

首先在kmp算法中最主要的next數(shù)組，這個(gè)數(shù)組標(biāo)志著截止到當(dāng)前下標(biāo)的最長(zhǎng)前綴后綴匹配子串字符個(gè)數(shù)，kmp算法里面，如果某個(gè)前綴是好前綴，即與模式串前綴匹配，我們就可以利用一定的技巧不止向前滑動(dòng)一個(gè)字符，具體看前面的講解。我們提前不知道哪些是好前綴，并且匹配過程不止一次，因此我們?cè)谧铋_始調(diào)用一個(gè)初始化方法，初始化next數(shù)組。

1.如果上一個(gè)字符的最長(zhǎng)前綴子串的下一個(gè)字符==當(dāng)前字符，上一個(gè)字符的最長(zhǎng)前綴子串直接加上當(dāng)前字符即可

2.如果不等于，需要找到之前存在的最長(zhǎng)前綴子串的下一個(gè)字符等于當(dāng)前子串的，然后設(shè)置當(dāng)前字符子串的最長(zhǎng)前綴后綴子串

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

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

然后開始利用next數(shù)組進(jìn)行匹配，從第一個(gè)字符開始匹配進(jìn)行匹配，找到第一個(gè)不匹配的字符，這時(shí)候之前的都是匹配的，接下來先判斷是否已經(jīng)是完全匹配，是直接返回，不是，判斷是否第一個(gè)就不匹配，是直接往后面匹配。如果有好前綴，這時(shí)候就利用到了next數(shù)組，通過next數(shù)組知道當(dāng)前可以從哪個(gè)開始匹配，之前的都不用進(jìn)行匹配。

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

到此這篇關(guān)于詳解Java中KMP算法的圖解與實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java KMP算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論