Liveddd's Blog

愛にできることはまだあるかい

P8112 [Cnoi2021]符文破译

发表于 更新于 分类于
本文字数： 1.9k 阅读时长 ≈ 4 分钟

不错的 Z 函数练习题。

很明显正着做不好搞，因为假如选取了当前某个前缀，很容易影响到后面的选取，并且不好优化。

经典正难则反的思想，考虑从后面逐渐选取模式串的前缀，这样就不会影响到前面前缀的选取。也就意味着，我们每次尝试选取一个文本串的一个后缀，使其等于模式串的前缀，然后进行下一步操作。

这是我们想到什么？ Z 函数不就是用来求出这东西的吗。考虑 DP，我们很容易写出状态转移方程：

有了这个，直接暴力 DP 是 $\mathcal O(n^2)$ 的，显然可以用线段树来维护，但 $\mathcal O(n\log n)$ 复杂度仍不允许我们通过此题。

还能继续优化吗？注意到对于所以可以转移到的 $f_i$ 一定是具有单调性，因为较短的后缀的代价一定不会大于较长的后缀的代价。而且根据 Z 函数 的性质，对于所有可以转移到的 $i$，$i+p_i$ 明显是单调递减的。这就转化为经典模型了，我们很容易用单调队列来优化，于是复杂度就变为了优秀的 $\mathcal O(n)$。

因为 $f_i$ 具有单调性，每次我们直接将其加入队尾就可以了。然后注意一些细节就可以了。

Code
 
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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e7+10,INF=1e9;
int n,m;
char a[N],b[N];
int z[N],p[N],f[N];
int l,r,q[N];
void Z(char *s,int n)
{
    z[1]=n;
    for(int i=2,l=0,r=0;i<=n;i++)
    {
        if(i<=r)z[i]=min(z[i-l+1],r-i+1);
        while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])z[i]++;
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }
}
void exkmp(char *s,int n,char *t,int m)
{
    Z(t,m);
    for(int i=1,l=0,r=0;i<=n;i++)
    {
        if(i<=r)p[i]=min(z[i-l+1],r-i+1);
        while(i+p[i]<=n&&s[i+p[i]]==t[p[i]+1])p[i]++;
        if(i+p[i]-1>r)l=i,r=i+p[i]-1;
    }
}//Z函数模板
int main()
{
    scanf("%d %d %s %s",&m,&n,b+1,a+1);
    exkmp(a,n,b,m);
    for(int i=1,j=0;i<=n;i++)
        j>i+p[i]?p[i]=0:j=i+p[i];//注意处理不可能转移到的情况
    memset(f,0x3f,sizeof(f));
    f[q[l=r=1]=n+1]=0;
    for(int i=n;i;i--)sa
    {
        if(!p[i])continue;
        while(l<=r&&q[l]>i+p[i])l++;
        f[i]=f[q[l]]+1;
        // while(l<=r&&f[q[r]]>=f[i])r--;
        //这里直接入队就可以了
        q[++r]=i;
    }
    if(f[1]<=INF)printf("%d\n",f[1]);
    else puts("Fake");
    return 0;
}

希望没有误人子弟 qwq。