发现自己 KMP 忘了，于是再学一遍。

懒得写了，直接写题。

P3375 【模板】KMP字符串匹配

挂一个模板

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string a, b;
    cin >> a >> b;

    int n = a.size(), m = b.size();
    vector<int> nxt(m + 1, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j && b[i] != b[j]) j = nxt[j];
        if (b[i] == b[j]) j++;
        nxt[i + 1] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j && a[i] != b[j]) j = nxt[j];
        if (a[i] == b[j]) j++;
        if (j == m) {
            cout << i - m + 2 << '\n';
        }
    }
    for (int i = 0; i < m; i++) {
        cout << nxt[i + 1] << " ";
    }

    return 0;
}

P2375 [NOI2014] 动物园

可以使用 DP 的思想解决这个问题。

令 \(f_i\) 表示第 \(i\) 位的前后缀个数，然后要求一个不重叠，于是在代码中加上这样一行就解决了

while ((j << 1) > (i + 1)) j = nxt[j];

求 \(f_i\) 显然了， 就是

void solve() {
    string s;
    cin >> s;

    int n = s.size();
    vector<int> nxt(n + 1), f(n + 1);
    f[1] = 1;
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) j = nxt[j];
        if (s[i] == s[j]) j++;
        nxt[i + 1] = j;
        // f[i + 1] = f[j] + 1;
    }
    for (int i = 2; i < n; i++) {
        f[i] = f[nxt[i]] + 1;
    }
    Z sum = 1;
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) j = nxt[j];
        if (s[i] == s[j]) j++;
        while ((j << 1) > (i + 1)) j = nxt[j];
        sum *= (f[j] + 1);
    }
    cout << sum.val() << "\n";
}