题意描述
Codeforces
链接
给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。
假设共有 \(k\) 个问号。
你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。
对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。
\(1\leq |s|,|t|\leq 10^5,|s|\cdot |t|\leq
10^7\)
解题思路
对于匹配字符串，显然我们可以用 KMP
思想解决。而对于匹配计数，我们可以使用 DP 解决。
我们可以先使用 KMP 求出 \(t\) 的
\(\text{next}\) 数组。
假设 \(s\) 长度为 \(n\)、\(t\)
长度为 \(m\)。我们可以设 \(f_{i, j}\) 表示使用 KMP 匹配时 \(s_i\) 匹配到 \(t_j\) 情况下匹配成功的次数。假设通过 KMP
匹配可得 \(s_{i + 1}\) 匹配 \(t_k\)，于是我们可以得到下列状态转移方程：
\[
f_{i + 1, k} = \max\{ f_{i + 1, k}, f_{i, j} + [k = m] \}
\]
于是我们只需要枚举 \(k\)
即可。而对于每个 \(t_i\)，我们可以预处理出 \(26\) 种字符所对应的 KMP
跳跃情况。这样可将时间复杂度降至 \(O(nm)\)。
接下来我们需要解决的是如何在时间复杂度为 \(O(m)\) 情况下预处理 \(t_i\) 的跳跃情况。假设 \(\text{jump}_{i, j}\) 表示已经匹配 \(t_i\)，在匹配 \(t_{i + 1}\) 与字符 \(j\) 进行匹配时跳转的坐标。通过 KMP
匹配，我们可以很显然得得出：\(\text{jump}_{i,
t_{i + 1}} = i + 1\)，且只有这种情况坐标增加，其余均为 \(\text{jump}_{i, j} = \text{jump}_{\text{next}_i,
j}\)。于是我们可以通过递推预处理该数组。时间复杂度 \(O(m)\)
时间复杂度为 \(O(nm)\)。
代码演示
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
| #include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::string s, t;
std::cin >> s >> t;
int n = s.size(), m = t.size();
s = ' ' + s, t = ' ' + t + ' ';
std::vector<int> next(m + 1);
next[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
while (j && t[j + 1] != t[i]) j = next[j];
if (t[j + 1] == t[i]) j++;
next[i] = j;
}
std::vector<std::array<int, 'z' + 1>> jump(m + 1);
jump[0][t[1]] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 'a'; j <= 'z'; j++) {
if (i < m && j == t[i + 1]) jump[i][j] = i + 1;
else jump[i][j] = jump[next[i]][j];
}
}
std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1, INT_MIN));
f[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
if (f[i][j] != INT_MIN) {
if (s[i + 1] == '?') {
for (int c = 'a'; c <= 'z'; c++) {
f[i + 1][jump[j][c]] = std::max(f[i + 1][jump[j][c]], f[i][j] + (jump[j][c] == m));
}
} else f[i + 1][jump[j][s[i + 1]]] = std::max(f[i + 1][jump[j][s[i + 1]]], f[i][j] + (jump[j][s[i + 1]] == m));
}
}
}
std::cout << *std::max_element(f[n].begin(), f[n].end()) << std::endl;
return 0;
}
|