写在前面
喜报：听了四遍都没学懂的KMP算法，终于在 gyy 大佬的耐心讲解下搞懂了，大佬orz！！！
正文
kmp算法本质上就是对模式串（要匹配的子串 两个串中短的那个 ）中很多重复的前缀和后缀索引起来，使得在一个地方失配了也不要紧，不用重新来的算法（看不懂不要紧）
下面我们就来详细介绍一下kmp的几个操作
预处理
| a | b | a | b | c |
|---|
用 \(nxt[i]\) 来存储对于模式串1~i中的最长前缀和后缀相等的长度
例如
| a | b | a | b | c |
|---|
在 \(i=3\) 时 前缀 \(a\) 等于后缀 \(a\) 所以 \(nxt[3]=1\)
在 \(i=4\) 时 前缀 \(ab\) 等于后缀 \(ab\) 所以 \(nxt[4]=2\)
而在 在 \(i=5\) 时 前缀没有等于后缀所以 \(nxt[5]=0\)
你会发现一个问题，其实 \(nxt[i]\) 就是 \(i\) 上一次在模式串出现的位置（那干嘛不叫 last 呢）
那聪明的你一定会问：这个是用来干嘛的呢？
别急，让我们来看适配操作
适配
| a | b | a | b | e | ... |
|---|---|---|---|---|---|
| a | b | a | b | c |
我们用 \(i\) 来表示文本串（被适配的串）的下标，\(j\) 来表示模式串的下标
我们先一项一项的配，当配到 \(j=5\) 时就发现两个串失配了，那怎么办，前面是不是白配了呢？
别担心，你会发现 \(j=5\) 的前一项 \(j=4\) 其实是适配的，于是就联想到我的 \(nxt[4]==2\) 其实如果和此时的 \(i=4\) 来配也是可以适配的，因为在第 \(j\) 项长度为 \(nxt[j]\) 前缀和后缀是相等的
所以我就将 \(j=nxt[j]\) 第 \(j+1\) 项也适配为止，然后就大功告成了！
提示
其实预处理 \(nxt[j]\) 数组就相当于模式串自身匹配，几乎和适配操作一样，不多赘述
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char a[N],b[N];
int nxt[N];
int main(){
cin>>a+1>>b+1;
int la=strlen(a+1),lb=strlen(b+1);
for(int i=1,j=0;i<=lb;i++){
while(j&&b[i+1]!=b[j+1]) j=nxt[j]; //如果i+1失配则找到i的上一个相同配子
if(b[i+1]==b[j+1]) j++;
nxt[i+1]=j;
}
for(int i=0,j=0;i<=la;i++){
while(j&&a[i+1]!=b[j+1]) j=nxt[j];
if(a[i+1]==b[j+1]) j++;
if(j==lb){
printf("%d\n",i-lb+2);
}
}
for(int i=1;i<=lb;i++){
printf("%d ",nxt[i]);
}
}