KMP算法是一种用于字符串匹配的算法，我们在介绍KMP算法之前，我们先介绍一下字符串匹配的朴素算法：

 

    题目：有长度为N的字符串P ， 长度为M的字符串S ， 问 P在S中匹配项的起始位置：

 

    双重循环，遍历S数组，每遇到一个新的S[i] 就要从 P[1]重新开始判断是否匹配，相当于一层一层的往后靠：’

 

    图示：

 

    于是，我们可以看到这样的算法会是O（NM）的，显然时间超限了！

 

    KMP算法的优点就在于利用了匹配失败后的信息，尽量的减少了模式串和模板串之间的匹配次数以达到快速匹配的作用，具体的实现是通过一个next数组来实现的。

    我们利用双指针i 和 j分别指向S 和 P，i不断在往后走，如果P[j+1] ==a[i]，j也往后移动一位， 如果j移动到了最后一位，那么我们就可以确定此时已经完成匹配了，但是！ 如果此时不匹配了，我们不是令i和j都回溯到前面的位置，我们保持i不变，j往前移动到next[j]的位置，注意这个next[1] ~ next[j] 的这一段与

j-next[j]+1 ~ j这一部分是完全重合的，这样的话，我们就省略了中间返回去重新匹配的过程：

 图示：

 

    我们可以发现，蓝色的那一部分重合了，我们直接将j移动到next[j]的位置，是因为在1 ~ j 这一段中只有从蓝色部分的起始开始才是重合的，前面根本不可能重合，所以我直接跳过去，省略了红蓝色的中间部分，极大的提高了算法时间效率，然后我再继续往后走，往后去判断就行了！

    然后就是next数组究竟该怎么实现了，我们会发现，next数组其实也就是P和P自身的匹配，对应每一个遍历的i，我们都记录一下指针移到i时，j指针会移到哪儿，也就是说找到移到i时的最长匹配子串，思路的实现与P和S一样；

上代码：

    

#include<bits/stdc++.h>
#define maxn 100010
#define maxm 1000010

using namespace std;
int ne[maxn];
char P[maxn],S[maxm];

int main()
{
int N,M;
cin>>N>>P+1>>M>>S+1;
for(int i = 2,j = 0 ;i<=N;i++){
while(j && P[i] != P[j+1]) j = ne[j];
if(P[i] == P[j+1]) j++;
ne[i] = j;
}

for(int i = 1, j = 0 ; i<=M;i++){
while(j && S[i]!=P[j+1])
j = ne[j];
if(S[i] == P[j+1]) j++;
if(j == N){
cout<<i - N << " ";
j = ne[j];
}
}
return 0;
}

 

需要注意的点：

·都是i 和 j+1去匹配，为什么呢，因为担心的是i 和 j匹配，j已经加了，i还没加，我这样满足的是判断j移到P的末尾时，是一定完全匹配了的！

·在构造next数组的时候，我令i从2开始，是因为如果从1开始就是自身等于自身了，没有意义！ 我要找的是前面的部分能否与后面的一部分重合！

·j满足条件后，不是返回到0，而是返回到next[j]，是因为两个匹配的子串可能是重叠的摆放的，不是规规矩矩地一个接着一个！