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

洛谷P3426 [POI2005]SZA-Template 题解


洛谷P3426 [POI2005]SZA-Template 题解

题目链接:P3426 [POI2005]SZA-Template

题意:你打算在纸上印一串字母。

为了完成这项工作,你决定刻一个印章。印章每使用一次,就会将印章上的所有字母印到纸上。

同一个位置的相同字符可以印多次。例如:用 aba 这个印章可以完成印制 ababa 的工作(中间的 a 被印了两次)。但是,因为印上去的东西不能被抹掉,在同一位置上印不同字符是不允许的。例如:用 aba 这个印章不可以完成印制 abcba 的工作。

因为刻印章是一个不太容易的工作,你希望印章的字符串长度尽可能小。

输入一个长度不超过 $5 \times 10^5$ 的非空字符串(只包含小写字母),代表要在纸上印的字符。

因为印章可以随便印,也就是无所谓什么顺序和数量

所以我们可以考虑什么样的情况可以继续

观察样例

ababbababbabababbabababbababbaba
ababbaba
     ababbaba
            ababbaba
                   ababbaba
                        ababbaba

最前面的ababbababbaba十分有趣

可以发现最左侧的一定是要印一次的(废话)

而重复印刷的显然和kmp的border有关

注:对字符串 $s$ 和 $0 \le r < |s|$ ,

若 $s$ 长度为 $r$ 的前缀和长度为 $r$ 的后缀相等,就称 $s$ 长度为 $r$ 的前缀是 $s$ 的 border。

摘自oi-wiki

考虑先求出border,然后用dp来推

设 $f_i$ 表示印刷 $s$ 的第 $i$ 个前缀的最小印章长度

上界为 $f_i=i$

这里 $f_i$ 在一定条件下是可以从 $\text{fail}_i$ 转移的

第一个看上去复杂,

其实就是 ababbababbaba 这样border有重叠的情况

用个桶维护即可,然后转移一下就好了

时间复杂度 $O(n)$

代码:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)
char s[N];
int n,fail[N],f[N],h[N];
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); n=strlen(s+1);
    for(int i=2,j=0; i<=n; i++)
    {
        while(j&&s[i]!=s[j+1])j=fail[j];
        if(s[i]==s[j+1])++j;
        fail[i]=j;
    }
    f[1]=1;h[1]=1;
    for(int i=2; i<=n; i++)
    {
        f[i]=i;
        if(h[f[fail[i]]]>=i-fail[i])
            f[i]=f[fail[i]];
        h[f[i]]=i;
    }
    cout << f[n] << '\n';
    return 0;
}

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