摘要：通過觀察發(fā)現(xiàn)，如果匹配字符串中有相同的子字符串，那么的變化會(huì)有所不同。所以這個(gè)值的變化跟目標(biāo)字符串沒什么關(guān)系，只跟自己的子字符串的重復(fù)性有關(guān)。的兩側(cè)子字符串相等，所以這時(shí)候倒數(shù)兩位位位代碼量不多但理解起來有點(diǎn)困難反正我理解了很久。

最近公司啟動(dòng)小程序項(xiàng)目中，在搜索模塊有這么個(gè)功能需求：當(dāng)用戶輸入搜索內(nèi)容時(shí)實(shí)時(shí)地請(qǐng)求服務(wù)器得到一組較高匹配度的搜索關(guān)鍵字，在這些關(guān)鍵字中高亮顯示用戶的匹配輸入。

例如輸入“中國”
搜索關(guān)鍵字為“中國共產(chǎn)黨”

那我就想到了KPM算法，就打開《大話數(shù)據(jù)結(jié)構(gòu)》這本書來看看KPM到底是什么東西，倒騰了很久，終于對(duì)KPM算法有一點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)了解，就來記錄一下。

傳統(tǒng)的字符串匹配算法是這樣子的：當(dāng)目標(biāo)字符串和匹配字符串在匹配過程中發(fā)生失配，目標(biāo)字符串下標(biāo)和匹配字符串下標(biāo)都要回溯，這會(huì)導(dǎo)致一些不必要的匹配判斷，舉個(gè)栗子。

當(dāng)匹配到第4位的時(shí)候，偶哦匹配失敗，那么將會(huì)從下面的位置開始匹配

但是我們明眼看去，很明顯是多余匹配判斷了嗎。
對(duì)沒錯(cuò)，傳統(tǒng)的匹配算法會(huì)只是很簡單的匹配回溯匹配回溯，時(shí)間復(fù)雜度為O((n-m)*m)，導(dǎo)致很多的匹配判斷是多余的，那么接下來的KPM算法就是解決這個(gè)笨重的問題的。

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是實(shí)現(xiàn)一個(gè)next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。時(shí)間復(fù)雜度O(m+n)。
注：一下i代表目標(biāo)字符串的下標(biāo)，j代表匹配字符串的下標(biāo)。
剛才講到，我們的KPM算法就是為了讓這沒必要的回溯發(fā)生，那么i不可變小，就只考慮變化j值了。通過觀察發(fā)現(xiàn)，如果匹配字符串中有相同的子字符串，那么j的變化會(huì)有所不同。所以這個(gè)j值的變化跟目標(biāo)字符串沒什么關(guān)系，只跟自己的子字符串的重復(fù)性有關(guān)。

next[j] = -1 // 當(dāng)j == 0時(shí)
        = max{k|0
例如：
j:       0 1 2 3 4
P:       A B A B C
next[j]:-1 0 0 1 2   

說白了就是j前的子字符串的重復(fù)字符有多少個(gè)，那么next[j]就是重復(fù)字符串個(gè)數(shù)。
next數(shù)組的作用就是KPM算法j值的回溯方案。
還是上面那么例子。當(dāng)i = 4, j = 4時(shí)C !== X ，那么這個(gè)時(shí)候j = next[j] = 2，所以只需進(jìn)行target[i(為4)]和pattern[j(為2)]的判斷，而pattern[0]和pattern[1]分別的判斷省略掉了。
說了那么多太干了，貼個(gè)代碼先。
var target = "ababxababc"
var pattern = "ababc"

function getKPMNext(str) {
    var i, j;
    var next = [];

    next[0] = -1;
    i = 0; j = -1;

    while(i < str.length - 1) {
        if (j == -1 || str[i] == str[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
    return next;
}

// j = next[j] next[j]的兩側(cè)子字符串相等，所以這時(shí)候str[i] == str[j] 倒數(shù)兩位== 4 5位 == 1 2位
console.log(getKPMNext("abxabaabxabxa"))

代碼量不多但理解起來有點(diǎn)困難（反正我理解了很久T_T）。j = -1的時(shí)候就是上述next數(shù)組在其他情況。
當(dāng)str[i] == str[j]的時(shí)候，那么i和j就很愉快地手牽手地前進(jìn)。
當(dāng)str[i] != str[j]的時(shí)候，那么j就要回溯。
然后就是KPM算法的主體了
function KPMMatch(target, pattern) {
    var i = 0, j = 0;
    var next = getKPMNext(pattern);

    while (i < target.length && j < pattern.length) {
        if (j == -1 || target[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if (j >= pattern.length) {
        return i - j;
    }
    return -1;
}

當(dāng)失配時(shí)j回溯，相對(duì)于傳統(tǒng)匹配省掉了不必要的匹配。