說明：

1. 文章內容為對KMP算法的總結，以及力扣例題；
2. 文章內容為個人的學習總結，如有錯誤，歡迎指正。

1. KMP算法

1.1 算法步驟

KMP算法通常用于字符串的匹配，解題分兩步：

1. 構建模式串的next數組。
   一般來說next數組就是前綴表（不太準確，但差不多是那個意思）。next[i]表明當第i個元素不匹配時應該回退到哪個位置：
   比如第i個元素不匹配，此時應尋找i之前的子串的最長相同前后綴的長度，這個長度的值就是next[i-1]的值。
   例：aab當i指向‘b’是發生了失配，此時應尋找b之前的子串，即‘aa’的最長相同前后綴的長度（=1），也就是說此時i指針應回退到下標為1的位置繼續比較
2. 匹配
   即模式串與主串的匹配。兩個指針i，j分別指向主串和模式串，若二者匹配則兩個指針后移；若發生失配，則指向模式串的指針j進行回退，重新匹配。

1.2 關于指針回退問題

關于指針回退的問題，我梳理一下：
例如：

主串='aabaabaaf'
模式串='aabaaf'

1. 匹配時，模式串的‘f’與主串的‘b’不匹配，此時模式串的指針應該回退，但是回退到哪個位置呢？KMP算法告訴我們應該回退到模式串‘b’的位置，為什么呢？

2. 因為不匹配的‘f’之前的子串——‘aabaa’的最長相同前后綴長度為2，即‘b’的下標。‘f’失配，但是‘aabaa’是和主串相匹配的，也就是說模式串中的“aa”（下標為3,4）與主串中的“aa”（下標為3,4）是相匹配的，而且子串“aabaa”中，后綴“aa”有最長相同的前綴“aa”（下標為0,1），也就是說這個前綴“aa”（下標0,1）和主串中的“aa”（下標為3,4）也是相匹配的，所以無需重復比較，直接將指針回退到模式串的‘b’位置繼續比較即可。
   

3. 所以next[i]中存儲的是i以及i以前的子串的最長相同前后綴長度。那么當i發生失配時，就要找i以前（0~i-1）的子串的最長相同前后綴長度是多少，然后回退到這個位置。
   比如‘f’失配時，要找‘f’之前的子串的最長相同前后綴長度（aabaa的最長相同前后綴長度）

2 . LeetCode例題

28. 找出字符串中第一個匹配項的下標

class Solution {
public:int strStr(string haystack, string needle) {vector<int> next(needle.size(),0);getNext(next, needle); //創建needle的next數組int j=0;for(int i=0; i<haystack.size(); i++){while(j>0 && haystack[i]!=needle[j])j = next[j-1];//發生失配，j進行回退if(haystack[i] == needle[j])j++;if(j == needle.size())return (i - needle.size() +1);//主串中出現了模式串，返回第一次出現模式串的下標}return -1; //主串中沒有出現模式串，返回-1}void getNext(vector<int>& next, string needle){int n = needle.size();int j = 0; //j指向前綴的末尾next[0] = 0;//初始化nums[0]for(int i=1; i<n; i++){//j從0開始，則i從1開始，i指向后綴的末尾，初始前后綴的長度都是1while(j>0 && needle[i]!=needle[j])j = next[j-1];//前后綴的末尾不匹配，j指針進行回退//j指針的回退相當于減小前綴的長度，當前綴末尾和后綴末尾相同時，此時就找到了needle[i]（包括needle[i]）之前的最長相同前后綴的長度；否則最長相同前后綴長度為0if(needle[i] == needle[j]){j++; //前后綴末尾相同時，同時后移i，j指針}next[i] = j;//將j的位置賦值給next[i]，表明第i個元素發生失配時應該回退到哪個位置}}
};