? ? ? ? 相信很多同學看到這篇文章的時候，已經被KMP拿捏了吧！KMP算法說難，倒也不是很難，手算都會，說不難吧，短短幾行代碼愣是看不懂，輾轉反側，翻書查閱，視頻講解，最后還是一頭霧水，百思不得其解（俺也一樣.jpg），去年準備初試的時候，學到這里覺得這個算法很神奇，就想搞懂它，但是想了好幾天都不太理解，考試也不考代碼，就暫且擱置了，奈何復試要上機，故打開力扣刷刷題，開篇就看到KMP，又喚起了我那該死的記憶，昨晚冥思苦想一個半小時，終于悟出正道，來跟大家分享分享……（好久沒更博客了，有點話癆）

????????還不會手動模擬的同學，可以先去學習一下它的原理，我覺得王道咸魚學長這個講得不錯4.2_2_KMP算法(舊版上)_嗶哩嗶哩_bilibili。接下來，完成這道題，就一起反向拿捏這個煩人的KMP吧！

---

轉自力扣

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

給你兩個字符串?haystack?和?needle?，請你在?haystack?字符串中找出?needle?字符串的第一個匹配項的下標（下標從 0 開始）。如果?needle?不是?haystack?的一部分，則返回??-1?。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標 0 和 6 處匹配。
第一個匹配項的下標是 0 ，所以返回 0 。

示例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現，所以返回 -1 。
提示：1 <= haystack.length, needle.length <= 104haystack和?needle僅由小寫英文字符組成?????

---

理解next數組：

先舉個例子理解一下：模式串為ababaa，手算可得出其next數組為：011234，next數組執行如下：

從圖中可發現，每次回溯，前面都是有相同匹配的子串，本身匹不匹配不重要（我之前理解是，本身也要匹配），例如，第四位的b回溯到第二位的b，第四位的b前面是aba，第二位的b前面是a，有重復的子串a；第六位的a回溯到第四位的b，第六位的a前面是ababa，第四位的b前面是aba，有重復的子串aba，但a和b并不相等；再來看代碼，

void getNext(int next[], string s)
{next[0]=-1;int i=0, j=-1;while(i<s.length()){if(j==-1||s[i]==s[j])//前面都匹配{i++;j++;next[i]=j;}else{j=next[j];}}
}

大家可以想象一下這個場景，拿兩個相同的串進行匹配，一前一后，相差一個位置，如果相同，說明到目前為止我都是跟你相同的，而i++、j++，使得 i 指針和 j 指針之前都是相同的（準確的來說是有相同子串），則next[ i ] = j，表示當 i 不匹配的時候，可以跳到 j。如果這兩個指針所指的不相等，說明 i 指針和 j 指針之前也是相同的，但是 i 指針和 j 指針失配了，只能讓 j = next[ j ]，讓 j 回溯，j 去找跟它前面相同的，讓 i 指針重新和新的 j 指針匹對；重復以上工作……

---

理解nextval數組：

這個就比next數組容易理解多了，還是拿上面的例子：模式串為ababaa，next數組為：011234，nextval數組為：010104；

例如，當第三位的a失配時，根據next數組要回溯到第一位的a，但是當第三位的a失配時，說明該元素不可能是a，回溯到第一位的a匹配則是多余操作，可以直接跳到它的next；當第六位的a失配時，根據next數組要回溯到第四位的b，因為a失配，只能說明該元素不是a，并不知道它是不是b，所以還要進行匹對；

代碼如下：（應該不難理解）

void getNextval(int nextval[], int next[], string s)
{nextval[0]=-1;for(int i=1; i<s.length(); i++){if(s[i]==s[next[i]])//該元素等于next里面的元素，因為字符串的首索引是0{nextval[i]=nextval[next[i]];}else{nextval[i]=next[i];}}
}

---

最后附上本題的ac代碼：

class Solution {
public:int strStr(string haystack, string needle){int next[10007]={0}, nextval[10007]={0};getNext(next, needle);getNextval(nextval, next, needle);int i=-1, j=-1;//i是主串，j是模式串int flag=0;//記錄是否匹配模式串while(1){if(j==-1||haystack[i]==needle[j]){i++;j++;}else{j=nextval[j];}if(j==needle.length())//匹配成功{flag=i-needle.length();return flag;}if(i==haystack.length())return -1;}}void getNext(int next[], string s){next[0]=-1;int i=0, j=-1;while(i<s.length()){if(j==-1||s[i]==s[j])//前面都匹配{i++;j++;next[i]=j;}else{j=next[j];}}}void getNextval(int nextval[], int next[], string s){nextval[0]=-1;for(int i=1; i<s.length(); i++){if(s[i]==s[next[i]])//該元素等于next里面的元素，因為字符串的首索引是0{nextval[i]=nextval[next[i]];}else{nextval[i]=next[i];}}}
};

可能大家還有一點疑惑：為什么我的下標是從-1開始，因為字符串的首字符下標是0，而書上的那些例題講解都是用字符數組存儲字符串，它的首字符下標是從1開始。

建議看懂理解了的同學去力扣重新做一下這道題，加深印象。希望能幫助到大家，歡迎指正！