写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

记录

kmp一般用来比较两组字符串（比如S、P）在哪一段相同。如果比较的时候不相同，那么指向P的指针会指向和暂停点前面和最开始相同的一段然后再次和S比较，直到找出来相等为止。一般统计在该点的重复数组有几个的时候用数组ne[i]表示。

下面举个例子：

例如：

S为abcababa；P为ababa。这里选取的均为从1开始读入。

1.计算ne[]的时候，利用双指针。i从2开始（因为第一个和自身相等没意义），j从0开始。

首先比较p[j+1]和p[i]的关系，这里即为a（1）和b（2），不相等，所以ne[i]=j=0，然后使得i++指向下一个字母。（注：这里的括号内的数字表示在字符串P内的序号，下同）

第二轮比较为a（1）和a（3），相等，j++，然后ne[2]就等于1。

第三轮先比较b（2）和b（4），相等，j++，ne[3]就等于2。

……

以此类推。

2.进行s和p的比较。

和上方类似的比较过程，这里不在阐述。值得一提的是，如果没有匹配成功，那么j指针将自动返回到与上述区间相同的点。

比如说当s中的i指向c（3）的时候，和p数列的a（3）不相等，这时候j就会更新到ne[2]=1（j+1=3），也就是把p重新从a（1）开始进行下一轮比较。直到得出答案。

下面是模板：

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6;
int n,m;
char p[N],s[N];
int ne[N];
int main()
{
    scanf("%d",&n);
    getchar();
    for(int i=1; i<=n; i++)
        scanf("%c",&p[i]);
    cin>>m>>(s+1);//和上面读入方法相同，只不过换了一种写法
    for(int i=2,j=0; i<=n; i++)
    {
        while (j&&p[i]!=p[j+1]) j=ne[j];//不相等则退一步，直到退到无路可退（j=0）
        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)//如果相同的数量和p字符串数量相同，则输出满足条件的第一个字符的序号，且同时更新
        {
            printf("%d ",i-n);
            j=ne[j];//为下一次的移动做准备
        }
    }
    cout << endl;
    return 0;
}