1. 問題引入

鏈接：leetcode_28

題目：s1字符串是否包含s2字符串，如果包含返回s1中包含s2的最左開頭位置，不包含返回-1

暴力方法就是s1的每個位置都做開頭，然后去匹配s2整體，時間復雜度O(n*m)

KMP算法可以做到時間復雜度O(n+m)，那這個算法是怎樣實現(xiàn)的呢？

2. 核心概念：最長公共前后綴

對于某個字符，不含該字符，前面的字符串的前后綴最大匹配長度，需要把這些數(shù)值傳給一個數(shù)組(next數(shù)組)，下標 i 表示第 i 個字符前的字符串(即從 0 ~ i-1 的字符串)的前后綴最大匹配長度

非常不好理解，請看示例：

這個玩意有什么用呢，看后面的核心步驟就理解了。

3. 核心過程

?【過程分解】

在比對的過程中，有兩個數(shù) x，y 記錄兩者對比到的下標

1）當兩字符相同，同時x++，y++，繼續(xù)對比下一個數(shù)據(jù)就好了

2）當s1和s2對應的字符不匹配時，則將y跳轉(zhuǎn)到next數(shù)組對應數(shù)據(jù)下標的字符，在此例子中是將y跳轉(zhuǎn)到下標6的位置

PS：每次跳轉(zhuǎn)時，如果此時y為0，只需要x++即可，因為y已經(jīng)沒有可以再退的字符了

---

跳轉(zhuǎn)之后：

此時x和y對應的下標依舊不匹配，再按照之前的邏輯，找此時y對應的next數(shù)組的數(shù)據(jù)，并跳轉(zhuǎn)，應該跳轉(zhuǎn)到3

---

再跳轉(zhuǎn)后：

當x和y對應的字符相同時，在x++，y++看下一個字符是否匹配，但是因為x已經(jīng)越界，但s2還沒匹配完，說明匹配失敗，返回 -1

【總結(jié)】

一共有兩種情況分別是

1. 兩字符相同，同時x++，y++，看后續(xù)是否相同
2. 兩字符不同，但y在下標0位置，只需要x++；若y不在0位置，將y定位到對應next數(shù)組相應數(shù)據(jù)的位置

在每一次操作結(jié)束時，都需要判斷x和y是否已經(jīng)越界

如果y等于s2的長度(包括x和y同時越界和只有y越界)，則說明匹配成功，結(jié)果為x-y （情況1）

否則，x越界，y沒越界，說明匹配失敗，返回-1? ? ?（情況2）

此處對應代碼的return返回值

【解惑】

1）為什么s2的0~5下標的字符和s1的7~12下標的字符對應，可以直接不用比對？

2）如果在s1的7下標之前還有與s2配對嗎？

沒有了，因為next數(shù)組就已經(jīng)決定了這是最長的前后綴匹配長度，再長就不匹配了

• 為什么會加速？

每次匹配時只需要從該字符對應的 next 數(shù)組的數(shù)開始匹配，相當于跳過了一部分的數(shù)據(jù)對比過程

【next 數(shù)組的創(chuàng)建】

有點類似動態(tài)規(guī)劃，通過前面的已知數(shù)據(jù)，推出當前的數(shù)據(jù)

操作過程：

若前一位的字符，與其next數(shù)組對應的下標的字符相同，則該字符對應的數(shù)為此下標數(shù)+1

如果不相同，若 next 數(shù)組對應數(shù)據(jù)不為0，則跳轉(zhuǎn)到對應下標，若為0則此字符對應 next 值為0

4. 例題

如果還不是很清晰，可以結(jié)合模版題和代碼一起分析，會更好理解

模版題：鏈接

參考代碼：

class Solution {
public:int strStr(string s1, string s2) {int m = s1.size(), n = s2.size();vector<int> next(n + 5);next[0] = -1;next[1] = 0; // 0和1下標next值默認確定int i = 2, cn = 0; // i表示當前對應下標，cn表示next值// 生成next數(shù)組// 結(jié)合前面的分析進行情況分類while (i < n){if (s2[i - 1] == s2[cn])next[i++] = ++cn;else if (cn > 0)cn = next[cn];elsenext[i++] = 0;}  int x = 0, y = 0;// x表示s1當前比對的位置// y表示s2當前比對的位置while (x < m && y < n){if (s1[x] == s2[y]){x++;y++;}else if (y == 0)x++;elsey = next[y]; }return y == n ? x - y : -1;}};