写在前面

本篇代码来源于皎月半撒花大佬的博客（指路）
加上了一些自己的理解，重写了代码注释，可能算转载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;
}