CF808G Anthem of Berland 题解

题目链接：CF808G Anthem of Berland

题意：

给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。

假设共有 \(k\) 个问号。

你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。

对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。

\(1\leq |s|,|t|\leq 10^5,|s|\times |t|\leq 10^7\)

样例三告诉你了，这题不是贪心。

设 \(f_i\) 表示前 \(i\) 个字符的最大答案

似乎不好转移，因为我们不知道上一个放的 \(t\) 在哪里

显然 \(f_i\) 可以从 \(f_{i-m}\) 转移过来，因为这里正好可以放得下一个 \(t\)

但是 \(t\) 是可以重叠放的，例如 \(t=\tt{aabaa}\)

于是我们直接跳 \(m\) 的 \(\tt{fail}\) 数组，然后一个个转移吗？

不，因为我们不知道 \(f_{i-(m-j)}\) 是否放了 \(t\)

注：放 \(t\) 的方法是把新的 \(t\) 的前缀和上一个 \(t\) 的后缀重合着放

不难发现这里要用到 \(\tt{kmp}\) ，正确性显然。

因此设 \(g_i\) 表示最后一个放的 \(t\) 以 \(i\) 结尾，前 \(i\) 个字符的最大答案 \[ g_i=\max\{g_{i-(m-j)}+1,g_i\} \] 因为 \(f_i\) 表示可以放或者不放 \(t\) ，所以转移方程是 \(f_i=\max\{f_{i-1},g_i\}\)

时间复杂度 \(O(|s| \times |t|)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

char s[N],t[N];
int n,m,f[N],g[N],fail[N];
bool check(int p)
{
    for(int j=1; j<=m; j++)
        if(s[p-j+1]!=t[m-j+1]&&s[p-j+1]!='?')
            return 0;
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s+1) >> (t+1);
    n=strlen(s+1); m=strlen(t+1);
    for(int i=2,j=0; i<=m; i++)
    {
        while(j&&t[i]!=t[j+1])j=fail[j];
        if(t[i]==t[j+1]) ++j;
        fail[i]=j;
    }
    for(int i=1; i<=n; i++)
    {
        f[i]=f[i-1];
        if(!check(i))continue;
        g[i]=f[i-m]+1;
        for(int j=fail[m]; j; j=fail[j])
            g[i]=max(g[i],g[i-(m-j)]+1);
        f[i]=max(f[i],g[i]);
    }
    cout << f[n] << '\n';
    return 0;
}