給字串$s, t$，
$s$由小寫字母跟?組成，如果把?都換成小寫字母，問最多能有幾個子字串與$t$相等?
$1\le |s|, |t|\le 10^5, |s|\cdot |t|\le 10^7$
首先看到測資第二個限制就能猜到這是個可以用$\mathcal{O}(|s||t|)$解決的問題。
以下字串$s, t$的索引值為從0開始，其餘則為1，
所以就直接定義dp[n][m]代表考慮s前$n$個字元，且這個前綴的最後$m$個字元與$t$的前$m$個字元相等，轉移式則為：
$$dp[n + 1][nxt(m, s[n])] = dp[n][m] + (m = t.size() ? 1 : 0)\ if\ s[n] \neq ?$$
$$dp[n + 1][nxt(m, c)] = dp[n][m] + (m = t.size() ? 1 : 0) \forall c = a..z\ Otherwise$$
其中$nxt(i, j)$為如果前$i$個字元再加上$j$這個字元的話，相同的前後綴會變成多少。
可以發現我們能用kmp來計算這函數，原理跟kmp蓋表類似。
而在dp時直接計算會使得轉移複雜度退化成$\mathcal{O}(|t|)$，所以必須先蓋表，但蓋表過程也是$\mathcal{O}(|t|^2)$。
可是可以用dp來優化他，定義kmp的failure function為$f$，則
$$nxt(m, c) = m+1\ if\ t[m] = c$$
$$nxt(m, c) = nxt(f(m-1), c)\ Otherwise$$
這樣就能$\mathcal{O}(|t|)$建$nxt$，讓dp能$\mathcal{O}(1)$轉移，整體複雜度$\mathcal{O}(|s||t|)$
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
const int INF = 0x3F3F3F3F;
vector<int> kmp(string &t) {
vector<int> dp(t.size());
for(int i = 1, j = 0; i < t.size(); i++) {
while(j && t[j] != t[i])
j = dp[j - 1];
if(t[j] == t[i])
j++;
dp[i] = j;
}
return dp;
}
signed main() { EmiliaMyWife
string s, t;
cin >> s >> t;
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, -INF)), nxt(t.size() + 1, vector<int>(26));
dp[0][0] = 0;
auto f = kmp(t);
for(int i = 0; i <= t.size(); i++) {
for(int j = 0; j < 26; j++) {
char c = 'a' + j;
if(i < t.size() && t[i] == c)
nxt[i][j] = i + 1;
else if(i)
nxt[i][j] = nxt[f[i - 1]][j];
}
}
for(int i = 0; i < s.size(); i++) {
dp[i][t.size()]++;
for(int j = 0; j <= t.size(); j++) {
if(s[i] == '?')
for(int c = 0; c < 26; c++)
dp[i + 1][nxt[j][c]] = max(dp[i + 1][nxt[j][c]], dp[i][j]);
else
dp[i + 1][nxt[j][s[i] - 'a']] = max(dp[i + 1][nxt[j][s[i] - 'a']], dp[i][j]);
}
}
dp[s.size()][t.size()]++;
cout << *max_element(dp[s.size()].begin(), dp[s.size()].end()) << '\n';
}
|