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