1.理解next[]數組的使用與來歷
2.求解next[]數組
一、kmp算法的原理
? ? ? ? 首先觀察暴力解法：假設主串為：abdxxabc，模式串為abxxabd。
暴力解法，就是對主串每個字符作為第一個字符，開始和模式串比較。
比如：從主串第一個字符a開始，比較到d發現不相等，然后從第二個字符b開始，直接不相等。以此類推，直到匹配或者到主串末尾。
? ? ? ? ? ?abxabc|abxabd? ? ? ????????????????????????abxabc|abxabd? ? ?...? ? ? ?abxabc|abxabd
? ? ? ? ? ?abxabd? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?abxabd? ? ? ? ? ? ? ??...? ? ? ? ? ? ? ? ? ? abxabd
? ? ? ? ? ? ?圖一? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? 圖二? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖三
比較操作的時間復雜度為O(m×n)。
kmp算法在此基礎上進行改進，關鍵點為，利用已經比較過的部分，比如圖一的abxabd。
? ? ? ? 當遇見不匹配的情況時，通過模式串的最長相等前后綴來確定下一次模式串比較的位置，并且不需要回退主串和模式串。前綴為不包含最后一個字符，包含第一個字符的子串，后綴為不包含第一個字符，保護最后一個字符的字串。
? ? ? ? 理解：匹配過程中，不匹配的情形只有兩種情況，其實也可以看成一種情況。第一種情況：第一個字符就不匹配，也就是說不匹配的字符前面沒有字符。如圖二。第二種情況：第n個字符不匹配，前n-1個字符匹配。如圖一。
? ? ? ?第一種情況由于第一個字符就不匹配，所以主串直接遍歷下一個字符，模式串還是第一個字符開始比較。第二種情況：如圖一，abxab是匹配的，此時，我們只需要檢查abxab這個字符串的最長相等前后綴的長度，最長相等前后綴為ab,長度為2。下一次我們直接比較模式串下標為2的字符x和此時主串不相等的字符c。然后重復上面的比較操作。
? ? ? ? 關鍵點是理解最長相等前后綴的性質。在已經匹配的字符串中，如何最長相等前后綴為0，也即是沒有相等的前后綴，那么顯然，由于已經匹配的字符串在模式串中為模式串的一個前綴，而在主串中為已經遍歷過的匹配的字符串的后綴，假設從i開始比較，到j不相等，主串i ~ j-1這一部分是模式串的一個前綴，因為肯定是從模式串的第一個字符開始比較的。而i - j-1這一部分如果沒有相等的前后綴，那么顯然不可能有和模式串匹配的部分，因為i~j-1是模式串的一個前綴，你都沒有后綴等于前綴，所以主串不用回退，直接遍歷下一個字符；如果有相等的前后綴，我們取最長的相等前后綴，i~j-1是模式串的一個前綴，假設最長的相等前后綴長度為2，也就是i， i+1是等于j-2, j-1，所以模式串的下一次比較的位置就是i+2，因為i~j-1也是主串的一部分，主串下一次比較的開始字符是j。
2.關鍵的最長相等前后綴的求解，也就是常說的next的數組。也就是前綴表。
一、暴力求解：兩個指針，left,right，分別指向后綴的開始，前綴的末尾。從最長的前后綴字串開始比較，逐漸縮短，直到不相等。
二、常用解法：kmp的思路，其實求解next數組的過程中也用到了kmp的算法思想。一個指針j，表示以i-1為尾部的前綴字符串的最長相等前后綴的長度，也即是j指向最長相等前綴的下一個字符。i遍歷字符串，從0開始。顯然，第一個前綴，最長相等前后綴長度為0。
比如字符串abcxabxabcxx。next[]數組：next[0]:前綴a的最長相等前后綴的長度；next[1]：前綴ab的最長相等前后綴的長度；next[2]：前綴abc的最長相等前后綴的長度，....表示以i結尾的前綴字符串的最長相等前后綴的長度。
for(i = 0; i < str.size(); ++i)遍歷一個一個求next[i]數組。
if (str[i] == str[j])? ?next[i] = ++j;
abcxabxabcxx: 假設此時i遍歷到了x，j為i-1結尾的前綴字符串的最長相等前后綴長度，也就是紅色部分表示的前綴字符串的最長相等前后綴長度，為2，也即是j指向最長相等前綴的下一個字符c。
其實就是next[i]是和next[i-1]有關系的。
關鍵是str[i] != str[j]， while(j > 0 && str[i] != str[j]) j = next[j-1];其實就是把字符串0~j看成模式串，
i-j~i看成主串，因為指針j，表示以i-1為尾部的前綴字符串的最長相等前后綴的長度，也即是j指向最長相等前綴的下一個字符。i-j~i-1是等于0-j-1的。
28. 找出字符串中第一個匹配項的下標 - 力扣（LeetCode）
參考代碼：
class Solution {
public:int strStr(string haystack, string needle) {//第一部分：求解next[]數組vector<int> next(needle.size());int j = 0;for(int i = 1; i < needle.size(); ++i){while(j > 0 && needle[j] != needle[i]){j = next[j - 1];}if(needle[i] == needle[j]){j++;}next[i] = j;}//第二部分：匹配文本串j = 0;for(int i = 0; i < haystack.size(); ++i){while(j > 0 && needle[j] != haystack[i])j = next[j - 1];if(haystack[i] == needle[j]){j++;}if(j == needle.size())return i - j + 1;}return -1;}
};
)
