0%

TIOJ 1091. 猜謎遊戲 (Guess)

題目大意

給長度為 )的字串 和長度為 )的字串 ,兩者皆由 AB 構成,求至少要從 中刪除多少字元,才能使 沒有任何一個子字串等於

題解

為將 砍成 ,滿足最長的「是 的前綴的 的後綴」長度是 ,至少需要砍幾個字元,要滿足題目要求的話, 就永遠不能是 ,所以其實只要不要讓任何 的狀態當轉移來源,最後答案就是

如果要得出狀態 ,如果把 砍掉,那它就是 ;不砍就要找到所有 ,滿足 的後綴,因為從 很難找,從 比較簡單,所以我們改成找狀態 )的轉移目標。

的轉移目標只會有兩個:

  1. 砍掉:
  2. 不砍:找到最大的 ,滿足 的後綴,沒有這個 ,然後

第一項很簡單,那第二項怎麼做呢?其實它根本就是 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 的部分是 ,狀態有 個,轉移時找轉移目標是 ,所以時間複雜度是 。因為字元只有兩種,所以也可以先用 的時間預處理接 AB 時的轉移目標,這樣複雜度就可以降到