Educational Codeforces Round 21 G. Anthem of Berland（DP+KMP）

原题链接：G. Anthem of Berland

题目大意：

给出一个含有 $?$ 字符的字符串 $s$ 和一个字符串 $t$，其中 $?$ 可以是 $26$ 个字符中任意一个字符。

假设 $s$ 有 $k$ 个 $?$ ，现在要你求出在所有 $26^k$ 种可能的情况中，$t$ 在 $s$ 出现的次数最大值为多少。

解题思路：

注意到 $|s|\cdot |t|\le 10^7$，考虑某种 $O(nm)$ 的做法。

定义 $dp[i]$ 为只考虑 $s$ 的前 $i$ 个字符，$t$ 能匹配的最大次数。

比较简单的想法就是考虑当前位置放和不放一整串 $t$ 。（前提是能放）

d p [ i ] = max ⁡ { d p [ i − 1 ] , d p [ i − ∣ t ∣ ] + 1 } \begin{aligned} dp[i] = \max\{dp[i-1],dp[i-|t|]+1\} \end{aligned} dp[i]=max{dp[i−1],dp[i−∣t∣]+1}​

但是显然这不能考虑到所有的情况，比如当 $s=ababa,t=aba$ 时，我们可以利用前面放下的 $t$ 串再做一次匹配，即：

$s=[ababa]$
$t=[aba\_\_]$
$t=[\_\_aba]$

此时 $dp[5]$ 可以从 $dp[3]$ 转移而来，发现这是一个 $border$，考虑用 $kmp$ 的 $next$ 数组来优化这个寻找可以从哪个 $border$ 转移过程。

但能从 $border$ 开始转移的前提是，这个位置 必须 放了一个 $t$ ，考虑下面的情况：

$s=[...ac[a]ba]$
$t=[...\_\_[a]ba]$

此时虽然 $[a]$ 位置确实是我们 $t=aba$ 的 $border$，但是其前面显然没有办法放下一个串 $t$，因而这个转移是不合法的。

所以我们还要考虑增加一个辅助数组 $g[i]$ 表示，当前只考虑前 $i$ 个位置，且第 $i$ 为 必须 放一个串 $t$ 的最大方案数。

那么此时转移就是考虑要不要从 $border$ 处转移即可：

d p [ i ] = max ⁡ j ∈ b o r d e r { d p [ i ] , g [ j ] + 1 } \begin{aligned} dp[i] = \max_{j \in border}\{dp[i],g[j]+1\} \end{aligned} dp[i]=j∈bordermax​{dp[i],g[j]+1}​

那么直接暴力匹配即可，考虑当前如果不能放 $t$，则 $dp[i]=dp[i-1]$ 。

否则考虑是否从 $border$ 转移而来，或者直接放下一个串 $t$ 。

其中串 $s$ 中的 $?$ 直接当通配符暴力匹配即可。

时间复杂度：$O(|s|\cdot |t|)$

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    std::string s, t;
    std::cin >> s >> t;

    int n = s.size(), m = t.size();
    s = '_' + s, t = '_' + t;

    std::vector<int> nxt(m + 1);
    for (int j = 2, p = 0; j <= m; ++j) {
        while (p && t[p + 1] != t[j]) p = nxt[p];
        p = nxt[j] = p + (t[p + 1] == t[j]);
    }

    auto check = [&](int l) {
        for (int i = 0; i < m; ++i) {
            if (s[l + i] != '?' && s[l + i] != t[i + 1]) {
                return false;
            }
        }
        return true;
    };

    std::vector<int> dp(n + 1), g(n + 1);
    for (int i = m; i <= n; ++i) {
        dp[i] = dp[i - 1];
        
        //假设能放串 t
        if (check(i - m + 1)) {
            g[i] = dp[i - m] + 1;
            for (int p = nxt[m]; p; p = nxt[p]) {
                g[i] = std::max(g[i], g[i - (m - p)] + 1);
            }
            dp[i] = std::max(dp[i], g[i]);
        }
    }

    std::cout << dp[n] << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    //std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}