嘘~ 正在从服务器偷取页面 . . .

CF808G Anthem of Berland 题解


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$ 个字符的最大答案

因为 $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;
}

文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
  目录