写在前面
本篇代码来源于皎月半撒花大佬的博客（指路）
加上了一些自己的理解，重写了代码注释，可能算转载plus罢
（好像每次都是这样的）（找好看的代码来背）
代码注释
以洛谷P3375为例。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
int nex[N], lens, lent;
char s[N], t[N];
int main(){
scanf("%s%s", s+1, t+1); // 输入
lens = strlen(s+1), lent = strlen(t+1); // 字符串长度
for(int i = 2, j = 0; i <= lent; i++){ // 枚举匹配串
// 求在i+1失配后应该返回到哪里（失配数组）
while(j && t[i] != t[j+1]) // 失配则继续往回跳
j = nex[j]; // 要保证 1~j 和 i-j+1~i 按位相等
if(t[j+1] == t[i]) j++; // 匹配成功则去到下一位置
nex[i] = j; // 得到匹配数组
}
for(int i = 1, j = 0; i <= lens; i++){ // 枚举文本串
while(j && s[i] != t[j+1]) // 失配则跳
j = nex[j]; // 跳跳跳 （直到跳回第一个字符）
if(t[j+1] == s[i]) j++; // 匹配成功则去到下一位置
if(j == lent){ // 如果1~lent都完全匹配
printf("%d\n", i-lent+1); // 输出匹配的开头
j = nex[j]; // 继续匹配
}
}
for(int i = 1; i <= lent; i++)
printf("%d ", nex[i]); // 输出失配数组
return 0;
}