前言

学KMP已经挺久了，但看到网上好多讲谜语的博客写一大堆也不知道在讲什么，大多都是tailor或者porter，萌新看到了很容易绕晕学不懂，因此在这里贴一下关于KMP的说人话又好懂的讲解，还有个人认为的一些重点与代码实现的认识偏差
好文!

Solution

$ne[i]$表示在模式串$p[]$中以$p[i]$结尾的后缀能够匹配的从1开始的非平凡（不包括自己）前缀的最长长度（这里注意模式串p的下标是从1开始的）
即满足在$p[1]$ ~ $p[i]$这一段字符串中，使得前$k$个字符恰好等于后$k$个字符的最大的$k$

求ne数组

虽然求$ne$数组与实现字符串匹配的代码大致相同，但是这里的$j$其实有别于下面求匹配的$j$，这里的j指的是$ne[i-1]$
求$ne$数组的过程本质上是$dp$，求匹配的过程本质上是双指针，是有微秒的区别的。

$i$从模式串P的第2位开始枚举，通过$ne[i-1]$推$ne[i]$,而$ne[1]=0$,即$j$的初始值为0
当$p[j + 1]$ 即 $p[ne[i-1] + 1] = p[i]$ 时 $ne[i] = ne[i - 1] + 1$ 即 $ne[i] = j + 1$
注意这里为什么是$j+1$? 我们每次倒退到$ne[j]$时，是比较字符$p[ne[j]+1]$是否等于$p[i]$,因为前$ne[j]$个字符是相等的
当$p[j + 1]$ 即 $p[ne[i - 1] + 1]!= p[i]$ 时，我们要想缩小$j$，把它改成小一点的值，再来试试 $P[i]$ 是否等于 $P[j + 1]$.

下面是文章原话，可以结合文章食用（now即是j，next数组即为ne数组，且文章中是从下标0开始的，这里和y总讲的都是从1开始的，注意区别就好）

now该缩小到多少呢？显然，我们不想让now缩小太多。因此我们决定，在保持“P[0]~P[x-1]的now-前缀仍然等于now-后缀”的前提下，让这个新的now尽可能大一点。 P[0]~P[x-1] 的公共前后缀，前缀一定落在串A里面、后缀一定落在串B里面。换句话讲：接下来now应该改成：使得 A的k-前缀等于B的k-后缀 的最大的k.　　您应该已经注意到了一个非常强的性质——串A和串B是相同的！B的后缀等于A的后缀！因此，使得A的k-前缀等于B的k-后缀的最大的k，其实就是串A的最长公共前后缀的长度 —— next[now-1]！

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
const int M = 1e6+5;
const int INF = 0x3f3f3f3f;
const int  mo = 1e9+7;

typedef pair<int,int> pii;

char p[N],s[M];
vector<int> ne(N);

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin >> n;
    cin >> p + 1;
    cin >> m;
    cin >> s + 1;
    /*ne[4] = 1
    ne[5] = 2
    abaaba
         i
    abaaba
      j
    */
    /*
     求ne数组
     虽然求ne数组与实现字符串匹配的代码大致相同，但是这里的j其实有别于下面求匹配的j，这里的j指的是ne[i-1]
     求ne数组的过程本质上是dp，求匹配的过程本质上是双指针，是有微秒的区别的
     i从模式串P的第2位开始枚举，通过ne[i-1]推ne[i],而ne[1]=0,即j的初始值为0

     当p[j + 1] 即 p[ne[i-1] + 1] = p[i] 时 ne[i] = ne[i - 1] + 1 即 ne[i] = j + 1 

     注意这里为什么是j+1? 我们每次倒退到ne[j]时，是比较字符p[ne[j]+1]是否等于p[i],因为前ne[j]个字符是相等的

     当p[j + 1] 即 p[ne[i - 1] + 1]!= p[i] 时，我们要想缩小j，把它改成小一点的值，再来试试 P[i] 是否等于 P[j + 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; 
}