基本思想

KMP 基本思想：匹配失敗時(shí)，設(shè)法利用這個(gè)已知信息，不要把"搜索位置"移回已經(jīng)比較過的位置探熔，繼續(xù)把它向后移亩鬼，移到第一個(gè)可能匹配的位置殖告。

比如：
母串：ABCDABC......
子串：ABCDABD......
當(dāng)?shù)?7 位 C 與 D 不匹配時(shí)，根據(jù)已知信息將子串移動(dòng)到有可能可以匹配的位置雳锋，移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值黄绩。

• 已匹配的字符數(shù) = 6
• 對(duì)應(yīng)的部分匹配值 = 2
• 移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值 = 4

部分匹配值

"部分匹配值"就是"前綴"和"后綴"的最長(zhǎng)的共有元素的長(zhǎng)度。

• "A" 的前綴和后綴都為空集玷过，共有元素的長(zhǎng)度為 0爽丹；
• "AB" 的前綴為 [A]，后綴為 [B]辛蚊，共有元素的長(zhǎng)度為 0粤蝎；
• "ABC" 的前綴為 [A, AB]，后綴為 [BC, C]嚼隘，共有元素的長(zhǎng)度 0诽里；
• "ABCD" 的前綴為 [A, AB, ABC]，后綴為 [BCD, CD, D]飞蛹，共有元素的長(zhǎng)度為 0谤狡；
• "ABCDA" 的前綴為 [A, AB, ABC, ABCD]，后綴為 [BCDA, CDA, DA, A]卧檐，共有元素為 "A"墓懂，長(zhǎng)度為 1；
• "ABCDAB" 的前綴為 [A, AB, ABC, ABCD, ABCDA]霉囚，后綴為 [BCDAB, CDAB, DAB, AB, B]捕仔，共有元素為 "AB"，長(zhǎng)度為 2；
• "ABCDABD" 的前綴為 [A, AB, ABC, ABCD, ABCDA, ABCDAB]榜跌，后綴為 [BCDABD, CDABD, DABD, ABD, BD, D]闪唆，共有元素的長(zhǎng)度為 0。

部分匹配實(shí)質(zhì)

有時(shí)候钓葫，字符串頭部和尾部會(huì)有重復(fù)悄蕾。比如，"ABCDAB" 之中有兩個(gè) "AB"础浮，那么它的"部分匹配值"就是 2（"AB" 的長(zhǎng)度）帆调。搜索詞移動(dòng)的時(shí)候，第一個(gè) "AB" 向后移動(dòng) 4 位（字符串長(zhǎng)度 - 部分匹配值）豆同，就可以來到第二個(gè) "AB" 的位置番刊。

部分匹配值的選取實(shí)質(zhì)上是基于貪心思想

移動(dòng)后的母串與子串的匹配部分（"ABCDAB"）的關(guān)系必須保證：母串的后綴等于子串的前綴，且盡量長(zhǎng)影锈。

比如芹务，母串 （"ABCDABC"） 與子串 （"ABCDABD"） 在第 7 位不匹配時(shí)，要把子串移到第一個(gè)可能匹配的位置鸭廷。在已匹配的 "ABCDAB" 中锄禽，第一個(gè)可能匹配的位置便是第 5 位 "A" 。

第一個(gè)可能匹配的位置實(shí)質(zhì)上就是匹配部分（子串前綴 "ABCDAB"）"前綴"和"后綴"的最長(zhǎng)的共有元素的首部靴姿。推導(dǎo)如下：

移動(dòng)后的母串與子串的關(guān)系必須保證：母串的后綴 X 等于子串的前綴 Y，且盡量長(zhǎng) --- (1)
既然屬于匹配部分磁滚，那么母串的該后綴 X 也就等于子串的后綴 Z --- (2)
由 (1) (2) 聯(lián)合可得佛吓，子串的前綴 Y 也就等于子串的后綴 Z
所以，匹配本身與母串無關(guān)垂攘，只與子串有關(guān)

KMP 實(shí)現(xiàn)

設(shè) P[j] 為子串匹配部分 B[1 ... j] 的部分匹配值维雇，則 P[j] 應(yīng)該是所有滿足 B[0 ... P[j] - 1] = B[j - P[j] + 1 ... j] 的最大值。由上面的推導(dǎo)可知晒他，P[j] 與母串 A 無關(guān)吱型，可單純從子串 B 推導(dǎo)而來。

那么陨仅，如何快速地預(yù)處理 P 數(shù)組呢津滞？我們可以通過 P[0]，P[1]灼伤，…触徐，P[j - 1] 的值來獲得 P[j] 的值。
對(duì)于 B = "ababacb"狐赡，假如我們已經(jīng)求出了 P[0]撞鹉，P[1]，P[2] 和 P[3]，看看我們應(yīng)該怎么求出 P[4] 和 P[5]

    0 1 2 3 4 5 6
B = a b a b a c b
P = 0 0 1 2 ? ?

P[3] = 2鸟雏，那么 P[4] 顯然等于 P[3] + 1享郊，因?yàn)橛?P[3] 可以知道，B[0, 1] 已經(jīng)和 B[2, 3] 相等了孝鹊，現(xiàn)在又有 B[2] = B[4]炊琉，所以 P[4] 可以由 P[3] 后面加一個(gè)字符得到。

    0 1 2 3 4 5 6
B = a b a b a c b
P = 0 0 1 2 3 ?

B[ P[4] + 1 ] != B[5] 惶室。那么温自，我們要考慮“退一步”了。我們考慮 P[5] 是否有可能由 P[4] 的情況所包含的子串得到皇钞，即是否 P[5] = P[ P[4] ] + 1悼泌。P[4] = 3 是因?yàn)?B[0 ... 2] 和 B[2 ... 4] 都是 "aba"；而 P[2] = 1 則告訴我們夹界，B[0]馆里、B[2] 和 B[4] 都是 "a" 。既然 P[5] 不能由 P[4] 得到可柿，或許可以由 P[2] 得到（如果 B[1] 恰好和 B[5] 相等的話鸠踪，P[5] 就等于 P[2] + 1 了）。顯然复斥，P[5] 也不能通過 P[2] 得到营密，因?yàn)?B[1] != B[5] 。事實(shí)上目锭，這樣一直推到 P[0] 也不行评汰，最后，我們得到痢虹，P[5] = 0 被去。

• 如果匹配成功，P[j] = P[j - 1] + 1
• 如果匹配失敗奖唯，j 倒退到 P[j - 1]惨缆，再繼續(xù)匹配，直到 j = 0 為止

// getNext P[i]: 滿足 B[0 ... P[i] - 1] = B[i - P[i] + 1 ... i] 的最大值（即匹配值）丰捷，P[i] = 0 時(shí)坯墨，表示匹配值為 0，不能再倒退
let j = 0, P = [];
P[0] = 0;
for (let i = 1; i < B.length; i ++) {
  while (j && B[j] !== B[i]) j = P[j - 1];
  if (B[i] === B[j]) j ++;
  P[i] = j;
}

// j 表示已經(jīng)匹配的長(zhǎng)度病往，即 A[i - j + 1 ... i] = B[0 ... j - 1]畅蹂，如果匹配失敗，倒退到 P[j - 1]
j = 0;
for (let i = 0; i < A.length; i ++) {
  while (j && A[i] !== B[j]) j = P[j - 1];
  if (A[i] === B[j]) j ++;
  if (j === B.length) {
    console.log('Pattern occurs with shift ', i - B.length + 1);
    j = P[j - 1];
  }
}

時(shí)間復(fù)雜度

KMP 的時(shí)間復(fù)雜度分析可謂攤還分析的典型荣恐。我們從上述程序的 j 值入手液斜。每一次執(zhí)行 while 循環(huán)都會(huì)使 j 減欣巯汀（但不能減成負(fù)的），而另外的改變 j 值的地方只有一行少漆。每次執(zhí)行了這一行臼膏，j 都只能加1；因此示损，整個(gè)過程中 j 最多加了 n 個(gè) 1渗磅。于是，j 最多只有 n 次減小的機(jī)會(huì)（j 值減小的次數(shù)當(dāng)然不能超過 n检访，因?yàn)?j 永遠(yuǎn)是非負(fù)整數(shù)）始鱼。這告訴我們，while 循環(huán)總共最多執(zhí)行了 n 次脆贵。按照攤還分析的說法医清，平攤到每次 for 循環(huán)中后，一次 for 循環(huán)的復(fù)雜度為 O(1) 卖氨。整個(gè)過程顯然是 O(n) 的会烙。這樣的分析對(duì)于后面 P 數(shù)組預(yù)處理的過程同樣有效，同樣可以得到預(yù)處理過程的復(fù)雜度為 O(m) 筒捺。