題目大意
給長度為 （）的字串 和長度為 （）的字串 ，兩者皆由 A、B 構成，求至少要從 中刪除多少字元，才能使 沒有任何一個子字串等於 。
題解
令 為將 砍成 ，滿足最長的「是 的前綴的 的後綴」長度是 ，至少需要砍幾個字元，要滿足題目要求的話， 就永遠不能是 ，所以其實只要不要讓任何 的狀態當轉移來源，最後答案就是 。
如果要得出狀態 ，如果把 砍掉，那它就是 ；不砍就要找到所有 ，滿足 是 的後綴，因為從 找 很難找，從 找 比較簡單，所以我們改成找狀態 （）的轉移目標。
的轉移目標只會有兩個：
- 把 砍掉：。
- 不砍：找到最大的 ，滿足 是 的後綴，沒有這個 就 ，然後 。
第一項很簡單，那第二項怎麼做呢？其實它根本就是 KMP，所以我們先做個 failure function：
然後就想成是現在在做字串匹配，已經匹配出等於 的子字串了，下一個字元是 ，用 KMP 的方式解決就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #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 的部分是 ，狀態有 個，轉移時找轉移目標是 ，所以時間複雜度是 。因為字元只有兩種，所以也可以先用 的時間預處理接 A 或 B 時的轉移目標，這樣複雜度就可以降到 。