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;
}