我們此前學(xué)了前綴樹(shù)Trie的實(shí)現(xiàn)原理以及Java代碼的實(shí)現(xiàn)。Trie樹(shù)很好，但是它只能基于前綴匹配實(shí)現(xiàn)功能。但是如果我們的需求是：一個(gè)已知字符串中查找子串，并且子串并不一定符合前綴匹配，那么此時(shí)Trie樹(shù)就無(wú)能為力了。

實(shí)際上這種字符串匹配的需求，在開(kāi)發(fā)中非常常見(jiàn)，例如判斷一個(gè)字符串是否包括某些子串，然后進(jìn)行分別的處理。

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

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

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

很明顯這種算法需要在一個(gè)雙重for循環(huán)中實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(m*n)，m為主串長(zhǎng)度，n為子串長(zhǎng)度。隨著字符串長(zhǎng)度的增長(zhǎng)，時(shí)間復(fù)雜度快速上升。

Java中字符串的contains方法實(shí)際上就是采用的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年共同提出的，稱(chēng)之為 Knuth-Morria-Pratt 算法，簡(jiǎn)稱(chēng) KMP 算法。

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

BF匹配失敗之后，主串和子串都會(huì)最大回溯，但是很多時(shí)候都是沒(méi)有必要的。例如對(duì)于主串a(chǎn)bababcd，子串a(chǎn)babc，第一次匹配之后，很明顯主串和子串會(huì)匹配失敗，但是我們能夠知道他們的能夠匹配的前綴串，即abab：

如果在第二次匹配的時(shí)候，主串不回溯，子串滑動(dòng)兩個(gè)字符長(zhǎng)度，那么我們就能在第二次的時(shí)候?qū)崿F(xiàn)匹配成功。

到這里，這種加速的方法已經(jīng)呼之欲出了，但是我們先介紹兩個(gè)重要概念：

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

例如主串a(chǎn)bcde，子串a(chǎn)bcc，那么在第一次匹配的時(shí)候，匹配前綴為abc。

2.最長(zhǎng)匹配長(zhǎng)度：對(duì)于每次匹配失敗后的匹配前綴串，其前綴子串（連續(xù)，且一定包括第一個(gè)字符，不包括最后一個(gè)字符）和后綴子串（連續(xù)，且一定包括最后一個(gè)字符，不包括第一個(gè)字符）中，相同的前后綴子串的最長(zhǎng)子串長(zhǎng)度，此時(shí)的前綴、后綴字串也被稱(chēng)為最長(zhǎng)真前綴、后綴子串。

• 例如匹配前綴abc，沒(méi)有匹配的前綴和后綴，那么其最長(zhǎng)匹配長(zhǎng)度為0。
• 例如匹配前綴cbcbc，最長(zhǎng)匹配的前綴和后綴子串為cbc，那么其最長(zhǎng)匹配長(zhǎng)度為3。
• 例如匹配前綴abbcbab，最長(zhǎng)匹配的前綴和后綴子串為ab，那么其最長(zhǎng)匹配長(zhǎng)度為2。

有了這兩個(gè)概念，那么我們才能進(jìn)行跳躍式滑動(dòng)，對(duì)于主串，在匹配失敗的位置不進(jìn)行回溯，對(duì)于子串，則是回溯（滑動(dòng)）到其匹配前綴的最長(zhǎng)匹配長(zhǎng)度的位置上繼續(xù)匹配，這樣就跳過(guò)了之前的部字符串的匹配，且只需要匹配剩下的部分字符串即可。

我們?cè)僭敿?xì)解釋下，這里子串跳過(guò)的到底什么？實(shí)際上它跳過(guò)的就是匹配前綴串的最長(zhǎng)匹配長(zhǎng)度串。
設(shè)主串a(chǎn)bababcd，子串a(chǎn)babc，第一次匹配失敗之后，主串匹配索引i=4，子串匹配索引j=4，此時(shí)匹配的相同前綴串為abab，它的最長(zhǎng)匹配長(zhǎng)度為2，即最長(zhǎng)前綴串a(chǎn)b和最長(zhǎng)后綴串a(chǎn)b。

那么第二次匹配之前，字串匹配索引j直接跳到第一匹配的相同前綴串的最長(zhǎng)匹配長(zhǎng)度的索引位置上即j=2。我們可以這么理解，主串的第一次匹配的相同前綴串的最長(zhǎng)匹配后綴，與子串第一次匹配的相同前綴串的最長(zhǎng)匹配前綴相等（或者說(shuō)重合）。這是我們?cè)诘讓右淮问∑ヅ渲蟮玫降挠行畔ⅲ诘诙纹ヅ鋾r(shí)自然可以利用起來(lái)，利用最長(zhǎng)的前后綴匹配信息，跳過(guò)這些多余的匹配，實(shí)現(xiàn)加速。（后續(xù)學(xué)習(xí)的AC自動(dòng)機(jī)也是采用了前后綴匹配的思想）

這就是KMP算法加速的核心原理，每次匹配失敗之后，利用匹配失敗的信息，找到最長(zhǎng)匹配長(zhǎng)度，然后主串不回溯，子串盡可能少的回溯，相比于BF算法，減少了沒(méi)必要的匹配次數(shù)。

next數(shù)組

基于上面的原理，我們知道可能會(huì)不止一次查找最長(zhǎng)匹配長(zhǎng)度，而且我們會(huì)發(fā)現(xiàn)，最長(zhǎng)匹配長(zhǎng)度的范圍只能在子串長(zhǎng)度范圍之內(nèi)，而且其計(jì)算結(jié)果只和子串有關(guān)。那么我們就可以先初始化一個(gè)數(shù)組，用來(lái)保存不同長(zhǎng)度的前綴的最長(zhǎng)匹配長(zhǎng)度。

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

假設(shè)子串為ababc，那么next數(shù)組值為：

假設(shè)子串為abcabdabcabc，那么對(duì)應(yīng)的next數(shù)組如下：

其實(shí)很好理解：

現(xiàn)在，我們的首要問(wèn)題變成了求next數(shù)組。

首先，切next數(shù)組的問(wèn)題實(shí)際上就是求最大的前、后綴長(zhǎng)度的問(wèn)題，那么我們可以使用最樸素的方式求解：

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

不難發(fā)現(xiàn)，求解next數(shù)組的時(shí)間復(fù)雜度為O(n^2)，是否有更快速的方法呢？當(dāng)然有，可以發(fā)現(xiàn)，在求next[i]的最長(zhǎng)匹配長(zhǎng)度的時(shí)候，next[0], next[1], … next[i-1]的結(jié)果已經(jīng)求出來(lái)了。因此我們嘗試?yán)么饲暗慕Y(jié)果直接推導(dǎo)出后面的結(jié)果。下面是分情況討論。

設(shè)子串為str=ababc，i=3，那么next[i-1]=1，即子串a(chǎn)ba的的最長(zhǎng)匹配長(zhǎng)度為1，那么str[next[i-1]]實(shí)際上就是最長(zhǎng)匹配子串前綴后一個(gè)字符，即str[1]=b。

如果str[i]=str[next[i-1]]，就相當(dāng)于在前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度的基礎(chǔ)上增加了一位，即next[i]=next[i-1]+1。如下圖：

如果str[i]!=str[next[i-1]]，此時(shí)就會(huì)復(fù)雜一些。此時(shí)我們需要縮短最長(zhǎng)匹配子串的長(zhǎng)度，具體怎么縮短呢？

設(shè)str = abcabdabcabc，設(shè)i = 11，即最后一個(gè)字符c，那么next[i-1] = 5，但是由于str[i] != str[next[i-1]]，即d != c，那么此時(shí)我們需要求i-1的最長(zhǎng)匹配長(zhǎng)度子串a(chǎn)bcab的最長(zhǎng)匹配長(zhǎng)度子串，即next[next[i-1]-1] = 2，然后判斷str[i]是否等于str[next[next[i-1]-1]]，如果相等則同第一種情況，否則繼續(xù)縮減直到next[next[i-1]-1]為0為止，此時(shí)表示當(dāng)前子串的最長(zhǎng)匹配長(zhǎng)度也為0。如下圖：

基于上面的規(guī)律，我們的改進(jìn)算法如下：

public static int[] getNext2(String k) {
    int[] next = new int[k.length()];
    char[] chars = k.toCharArray();
    //i表示匹配的字符索引，pre表示前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度，即next[i-1]
    int i = 1, pre = next[i - 1];
    while (i < k.length()) {
        //如果新增的字符與前一個(gè)子串的最長(zhǎng)匹配子串前綴的后一個(gè)字符相等
        if (chars[i] == chars[pre]) {
            //next[i]=next[i-1]+1
            pre++;
            next[i] = pre;
            //繼續(xù)后移
            i++;
        }
        //如果不相等，且前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度不為0
        //那么求i-1的最長(zhǎng)匹配長(zhǎng)度子串的最長(zhǎng)匹配長(zhǎng)度子串，即pre=next[next[i-1]-1]
        //然后在下一輪循環(huán)中繼續(xù)比較chars[i] == chars[pre]，此時(shí)i并沒(méi)有自增
        else if (pre != 0) {
            //next[next[i-1]-1]
            pre = next[pre - 1];
        }
        //如果不相等，且前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度為0，那么說(shuō)明當(dāng)前子串的最長(zhǎng)匹配長(zhǎng)度也為0
        else {
            //當(dāng)前子串的最長(zhǎng)匹配長(zhǎng)度為0
            next[i] = 0;
            //繼續(xù)后移
            i++;
        }
    }
    return next;

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

KMP匹配

有了next數(shù)組，那么KMP算法就很容易實(shí)現(xiàn)了。

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

1.如果字符相等則推進(jìn)i、j，并且判斷如果匹配到了一個(gè)完整的子串，那么返回起始索引。

2.如果不相等：

• 如果當(dāng)前子串進(jìn)度為0，那么子串不需要回退，主串向后推進(jìn)i，重新開(kāi)始匹配；
• 如果當(dāng)前子串進(jìn)度不為0，那么子串進(jìn)度需要回退到next[j-1]的位置，此前的位置不再需要匹配，主串不需要向后推進(jìn)i，隨后重新開(kāi)始匹配。

如果i進(jìn)度匹配完畢，那么退出循環(huán)，表示沒(méi)有匹配到任何完整的子串，返回-1。

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

KMP全匹配

上面我們的實(shí)現(xiàn)是返回第一個(gè)匹配到的模式串的起始索引，那么如果我們需要返回所有匹配到的模式串的起始索引呢？
其實(shí)也很簡(jiǎn)單。在每次匹配某個(gè)字符成功之后判斷，如果匹配到了一個(gè)完整的子串，那么我們求起始索引并且加入結(jié)果集，然后子串點(diǎn)位j需要回退，繼續(xù)循環(huán)。

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

總結(jié)

KMP算法是一種優(yōu)化的字符串匹配算法，m為主串長(zhǎng)度，n為子串長(zhǎng)度。由于構(gòu)建了 next 數(shù)組，空間復(fù)雜度為 O(m)。匹配時(shí)主串不會(huì)回退，子串回退不會(huì)超過(guò)n，總體算法時(shí)間復(fù)雜度為O(m+n)。

next數(shù)組是實(shí)現(xiàn)算法加速的關(guān)鍵，它的核心是查找最長(zhǎng)前后綴匹配長(zhǎng)度，這也是理解KMP算法的核心。

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

最新評(píng)論