前言
狗屁不是，建议别看！！！
题目链接
P3375 【模板】KMP 字符串匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析
先给个例子
s1：ABCABCABB
s2：ABCABB
若使用朴素算法匹配，当匹配到
s1：ABCAB C ABB
s2：ABCAB B
时，朴素算法会跳出，然后匹配下一位。
最终匹配到
s1：ABC ABCABB
s2： ABCABB
匹配成功
我们发现其中
s1：ABC AB CABB
s2： AB CABB
AB二位在第一次匹配中已经匹配过了
那么如何简化该重复操作呢？
定义next数组（next是关键字，不要用作变量名）
next[i]表示的是s2在i之前的最长的完全相同的前缀后缀长度（不能为整个字符串）
例如：ABCAB
前缀有A、AB、ABC、ABCA
后缀有B、AB、CAB、BCAB
最长的完全相同的前缀后缀为AB，所以next=2
回到第一次匹配中，当匹配到
s1：ABCAB C ABB
s2：ABCAB B
时，即指针i（s1）=6，指针j（s2）=6；
由于next[5]=2，即s2中末尾AB（4，5）与开头AB（1，2）是等价的，并且s2末尾AB与s1中间的AB（4，5）是等价的
所以s1中间的AB可以与s2开头的AB匹配且最长
满足最长即前面的B、C都无法完成匹配
令此时j=next[j-1]+1，再进行下一次匹配
直到j=6（len s2）时匹配结束
那么如何计算next呢？
令i为当前所计算字符串的末尾，j为前缀的末尾
与两个字符串匹配类似
当a[i]!=a[j]时 令j=next[j-1]+1
代码
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int N=1000006;
5
6 char a[N],b[N];
7 int ne[N];
8
9 int main(){
10 scanf("%s %s", a+1, b+1);
11 int an=strlen(a+1),bn=strlen(b+1);
12 int j=0;//i，j指需要匹配的字符的前一个值
13 for(int i=1;i<bn;i++){
14 while(j>0&&b[j+1]!=b[i+1]) j=ne[j];
15 if(b[j+1]==b[i+1]) j++,ne[i+1]=j;
16 }
17 j=0;
18 for(int i=0;i<an;i++){
19 while(j>0&&b[j+1]!=a[i+1]) j=ne[j];
20 if(b[j+1]==a[i+1]) j++;
21 if(j==bn){
22 printf("%d\n", i+1-bn+1);
23 j=ne[j];
24 }
25 }
26 for(int i=1;i<=bn;i++) cout<<ne[i]<<" ";
27 return 0;
28 }