怎么总是忘。
默认 \(s\) 为 0-indexed。
首先前缀函数：\(\pi[i]\) 怎么求。
由于 \(\pi[i + 1] - \pi[i] \le 1\)，所以最好情况就是 \(s[i + 1] = s[\pi[i]]\)，此时 \(\pi[i + 1] = \pi[i] + 1\)，如果失配，我们需要找到一个最大的 \(j\) 满足 \(s[0 \sim j - 1] = s[i - j + 1]\)，显然 \(j = \pi[i]\)。然后不停跳即可。
然后 KMP，每次失配后需要找一个新的前缀匹配当前后缀，显然跳前缀函数就行。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 1e6 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, m, pi[N];
char s[N], t[N];
basic_string<int>ans;
void main() {cin >> s >> t; n = strlen(s); m = strlen(t);for (int i = 1; i < m; i++) {int j = pi[i - 1];while (j && t[i] != t[j]) j = pi[j - 1];if (t[i] == t[j]) j++;pi[i] = j;}int j = 0;for (int i = 0; i < n; i++) {while (j && s[i] != t[j]) j = pi[j - 1];if (s[i] == t[j]) j++;if (j == m) {ans += i - m + 1;j = pi[j - 1];}}for (int x : ans) cout << x + 1 << '\n';for (int i = 0; i < m; i++) cout << pi[i] << " \n"[i == m - 1];
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}