1. KMP算法是应用于字符串匹配问题的。比方说给你两个字符串，寻找其中一个字符串是否包含另一个字符串啊这样的问题。
一般来说，我们可以暴力的去跑，从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾。这样的话时间复杂度就是O(n*m)，但是利用KMP的话时间复杂度就会降低到O(n+m)。
其实算法的代码很简单，但是关键是理解nextt 数组是怎么求的。
至于为什么移动会很节省时间的图片可以看https://www.cnblogs.com/yjiyjige/p/3263858.html，这个说的挺好的。
2. next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。最长前缀是从第一个字符开始，同理最长后缀是要到最后一个字符。
比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同是abc。 可以看样例，手动写一下nextt 数组的值。
字符串 s = "ababaaababaa";
nextt、[1] = -1,代表着除了第一个元素，之前前缀后缀最长的重复子串，这里是空 ,即""，没有，我们记为-1，代表空。（0代表1位相同，1代表两位相同，依次累加）。
nextt[2] = -1，即“a”，没有前缀与后缀，故最长重复的子串是空，值为-1；
nextt[3] = -1，即“ab”，前缀是“a”，后缀是“b”，最长重复的子串“”；
nextt[4] = 1，即"aba"，前缀是“ab”，后缀是“ba”，最长重复的子串“a”；
nextt[5] = 2，即"abab"，前缀是“aba”，后缀是“bab”，最长重复的子串“ab”；
nextt[6] = 3，即"ababa"，前缀是“abab”，后缀是“baba”，最长重复的子串“aba”；
nextt[7] = 1，即"ababaa"，前缀是“ababa”，后缀是“babaa”，最长重复的子串“a”；
nextt[8] = 1，即"ababaaa"，前缀是“ababaa”，后缀是“babaaa”，最长重复的子串“a”；
nextt[9] = 2，即"ababaaab"，前缀是“ababaaa”，后缀是“babaaab”，最长重复的子串“ab”；
nextt[10] = 3，即"ababaaaba"，前缀是“ababaaab”，后缀是“babaaaba”，最长重复的子串“aba”；
nextt[11] = 4，即"ababaaabab"，前缀是“ababaaaba”，后缀是“babaaabab”，最长重复的子串“abab”；
nextt[12] = 5，即"ababaaababa"，前缀是“ababaaabab”，后缀是“babaaaababa”，最长重复的子串“ababa”；
3. KMP的核心代码：就是先对目的串求出对应的nextt 数组（用自身去匹配自己），然后再用匹配串去匹配，
void getnext()
{
nextt[0]=-1;
int k=-1;
for(int i=1;i<len2;i++)
{
if(k>-1&&s2[k+1]!=s2[i])
k=nextt[k];
if(s2[k+1]==s2[i])
k=k+1;
nextt[i]=k;
}
}
int KMP()
{
getnext();
// for(int i=0;i<m;i++)
// cout<<nextt[i]<<" ";
// cout<<endl;
int k=-1;
for(int i=0;i<len1;i++)
{
while(k>-1&&s2[k+1]!=s1[i])
k=nextt[k];
if(s2[k+1]==s1[i])
k=k+1;
if(k==len2-1)
{
k=-1;
cnt++;
}
}
return cnt;
}
4. 这块代码的解释
if(k>-1&&s2[k+1]!=s2[i])
k=nextt[k];
为什么会k=nextt[k] ？
因为当匹配失败的时候，我们要向前回溯，找到最长的刚好匹配的最长前缀和最长后缀。
可以看下这个图：
next[j] == k;
next[k] == 绿色色块所在的索引;
next[绿色色块所在的索引] == 黄色色块所在的索引;
1.由"next[j] == k;"这个条件，我们可以得到A1子串 == A2子串（根据next数组的定义，前后缀那个）。
2.由"next[k] == 绿色色块所在的索引;"这个条件，我们可以得到B1子串 == B2子串。
3.由"next[绿色色块所在的索引] == 黄色色块所在的索引;"这个条件，我们可以得到C1子串 == C2子串。
4.由1和2(A1 == A2，B1 == B2)可以得到B1 == B2 == B3。
5.由2和3(B1 == B2， C1 == C2)可以得到C1 == C2 == C3。
6.B2 == B3可以得到C3 == C4 == C1 == C2
这样的话，我们向前回溯就能很快的找到满足题意的最大匹配。