題目大意

給長度為 $M$（$2 \leq M \leq 100$）的字串 $A$ 和長度為 $N$（$M < N \leq 1000$）的字串 $B$，兩者皆由 A、B 構成，求至少要從 $B$ 中刪除多少字元，才能使 $B$ 沒有任何一個子字串等於 $A$。

題解

令 $dp[i][j]$ 為將 $B_{1..i}$ 砍成 $B'$，滿足最長的「是 $A$ 的前綴的 $B'$ 的後綴」長度是 $j$，至少需要砍幾個字元，要滿足題目要求的話，$j$ 就永遠不能是 $M$，所以其實只要不要讓任何 $j=M$ 的狀態當轉移來源，最後答案就是 $\min_{0 \leq j < M} dp[N][j]$。

如果要得出狀態 $dp[i][j]$，如果把 $B_i$ 砍掉，那它就是 $dp[i-1][j]+1$；不砍就要找到所有 $k$，滿足 $A_{1..j}$ 是 $A_{1..k} + B_i$ 的後綴，因為從 $j$ 找 $k$ 很難找，從 $k$ 找 $j$ 比較簡單，所以我們改成找狀態 $dp[i][k]$（$k < M$）的轉移目標。

$dp[i][k]$ 的轉移目標只會有兩個：

1. 把 $B_{i+1}$ 砍掉：$dp[i + 1][k] = dp[i][k] + 1$。
2. 不砍：找到最大的 $j$，滿足 $A_{1..j}$ 是 $A_{1..k} + B_i$ 的後綴，沒有這個 $j$ 就 $j=0$，然後 $dp[i + 1][j] = dp[i][k]$。

第一項很簡單，那第二項怎麼做呢？其實它根本就是 KMP，所以我們先做個 failure function：

$$F_A(i) = \max \{1 \leq k < i\ |\ A_{1..k} = A_{i-k+1..i}\}\ \text{or 0 if no such }k$$

然後就想成是現在在做字串匹配，已經匹配出等於 $A_{1..k}$ 的子字串了，下一個字元是 $B_i$，用 KMP 的方式解決就行了。

#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

int main(){
    StarBurstStream

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

    int m = a.size(), n = b.size();
    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, MAX));
    dp[0][0] = 0;
    a = ' ' + a; b = ' ' + b;

    vector<int> f(m + 1);
    int now = 0;
    for(int i = 2; i <= m; i++){
        while(now == m || (now != 0 && a[now + 1] != a[i])) now = f[now];
        if(a[now + 1] == a[i]) now++;
        f[i] = now;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            now = j;
            while(now != 0 && b[i + 1] != a[now + 1]) now = f[now];
            if(b[i + 1] == a[now + 1]) now++;
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][j]);
        }
    }

    cout << *min_element(dp[n].begin(), dp[n].begin() + m) << "\n";

    return 0;
}

蓋 failure function 的部分是 $O(M)$，狀態有 $O(NM)$ 個，轉移時找轉移目標是 $O(M)$，所以時間複雜度是 $O(NM^2)$。因為字元只有兩種，所以也可以先用 $O(M^2)$ 的時間預處理接 A 或 B 時的轉移目標，這樣複雜度就可以降到 $O(NM)$。