1.KMP算法是什么？
KMP算法是一个模式匹配算法，可以大大避免重复遍历的情况（也就是避免掉了传统的朴素模式匹配算法的低效）
因此我们KMP算法用于解决的就是字符串匹配问题
因此，假设我们有两个串，一个文本串，一个模式串
文本串：AABAABAAF
模式串：AABAAF
我们要进行匹配，传统的朴素算法是将底下模式串的第一位与文本串的第一位匹配，配对上了都走下一位，不匹配了就让模式串的第一位与文本串的第二位进行匹配，然后反复进行以上操作，直到匹配了 整个模式串才停止，但是这样真的高效吗？
我们在第一轮，只有最后一个没有匹配上，未必让两个串的指针都回溯，只需要让模式串指针回溯即可，比如说最后一个F出错了，我们可以选择回溯到模式串的第四个（A），在对上述字符串进行匹配，如果匹配到了，就继续，没有匹配到就继续回溯我们的模式串指针。
2.那么我们该如何确定要回溯的位置呢？
我们通常会用一个next数组来确定返回哪个位置，我们的next数组其实就是一个前缀表（同时也可以称为最长相等前后缀）
（1）前缀表的基础
前缀：必须包含第一个字母但不包含最后一个字母的连续子串
后缀：必须包含最后一个字母但不包含第一个字母的连续子串
前缀表：最长相等前后缀（即这个字符串的前缀和后缀相等，还是最长的那个）
那么我们就来举一个例子，例如模版串是AABAAF
前一个：A，只有一个字母，没有前缀也没有后缀，最长相等前后缀为0；
前两个：AA，前缀为A，后缀为A，最长相等前后缀为1；
前三个：AAB，前缀为A，AA,后缀为B,AB，最长相等前后缀为0；
前四个：AABA，前缀为A,AA,AAB，后缀为A,BA,ABA，最长相等前后缀为1；
前五个：AABAA,前缀为A,AA,AAB,AABA,后缀为，A,AA,BAA,ABAA,最长相等前后缀为2；
前六个：AABAAF，前缀为A,AA,AAB,AABA,AABAA,后缀为F,AF,AAF,BAAF,ABAAF，最长相等前 后缀为0；
我们回退之后就可以不重复比较了，这是为什么呢？
因为前一位的next数组值记录了该子串的最长相等前后缀，那么我们只需要从最长相等的前缀的下一位开始进行比较就可以，而由于数组的下标从0开始，个数从1开始，所以next数组所记录的个数刚好就是最长前缀下一位的下标
（2）next数组的代码求法
void getnext1()//得到next数组
{
int i=-1,j=0;//i是前缀末尾位置，j是后缀末尾位置
next1[0]=-1;//标记next数组首位置是-1 ，我们这里用的求next数组是前缀表向右错一个位置的写法
while(j<len2)//后缀末尾没有超过模版串的最后
{
if(i==-1||s2[i]==s2[j])//当现在是开头或者匹配上的时候
{
i++;
j++;
next1[j]=i;
}
else
{
i=next1[i];//回溯前缀末尾
}
}
}3.KMP算法的实现过程
KMP算法，就是当你本位置回溯失败之后，要回溯到你当前位置next数组所指向的位置，这样可以避免朴素暴力解法的重复匹配，减小时间开销
代码实现：
void kmp()
{
int i=0,j=0;//i是文本串指针，j是模式串指针
while(i<len1)//当没有超过文本串时
{
if(j==-1||s1[i]==s2[j])//当文本串指针指向初始位置，或者说文本串和模式串匹配上的时候
{
i++;//文本串指针向后挪一位
j++;//模式串指针向后挪一位
}
else
{
j=next1[j];//如果匹配不上，就返回当前位置的next数组
}
if(j==len2)
{
printf("YES");//如果能匹配完，说明文本串里有模式串，可以匹配上，输出YES
}
}
}4.KMP算法相应例题
（1）第一题：模版KMP
题解：这题就是一个标准的kmp的题，没有任何的难度，得到next数组后直接进行kmp进行匹配
如果能够达到模式串的末尾，就说明能够进行匹配，然后输出匹配的起始位置即可，即i-len(2)+1
然后后续输出next数组；
#include <bits/stdc++.h>
using namespace std;
int n,k,len1,len2;
int next1[1000001];
char s1[1000001];//文本串
char s2[1000001];//模版串
void getnext1()//得到next数组
{
int i=-1,j=0;//j是后缀末尾位置，i是前缀末尾位置
next1[0]=-1;//标记next数组首位置是-1
while(j<len2)//后缀末尾没有超过模版串的最后
{
if(i==-1||s2[i]==s2[j])//当现在是开头或者匹配上的时候
{
i++;
j++;
next1[j]=i;
}
else
{
i=next1[i];
}
}
}
void kmp()
{
int i=0,j=0;//i是文本串指针，j是模式串指针
while(i<len1)//当没有超过文本串时
{
if(j==-1||s1[i]==s2[j])
{
i++;
j++;
}
else
{
j=next1[j];
}
if(j==len2)
{
printf("%d\n",i-len2+1);
j=next1[j];
}
}
}
int main()
{
scanf("%s",s1);
scanf("%s",s2);
len1=strlen(s1);
len2=strlen(s2);
getnext1();
kmp();
for(int i=1;i<=len2;++i)
printf("%d ",next1[i]);
return 0;
}（2）第二题：无线传输
题解：这题其实更加方便我们去了解kmp的真正过程，以及了解next数组的真正含义，通过题目我们就会发现，其实s2的最短长度，其实就是L-next[L]；
因此AC代码：
#include<bits/stdc++.h>
using namespace std;
int l;
char s[1000005];
int len;
int sum;
int next1[1000005];
void getnext1()
{
int i=-1,j=0;
next1[0]=-1;
while(j<len)
{
if(i==-1||s[i]==s[j])
{
i++;
j++;
next1[j]=i;
}
else
{
i=next1[i];
}
}
}
int main()
{
scanf("%d",&l);
scanf("%s",s);
len=strlen(s);
getnext1();
printf("%d",l-next1[l]);
return 0;
}
