相信很多同学看到这篇文章的时候，已经被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开始。
建议看懂理解了的同学去力扣重新做一下这道题，加深印象。希望能帮助到大家，欢迎指正！
