洛谷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\) 转移的 \[ f_i = \begin{cases} f_{\text{fail}_i},& \exists \, j \ge i-\text{fail}_i,f_j = f_{\text{fail}_i}, \\\\i,&\text{default.} \end{cases} \] 第一个看上去复杂，

其实就是 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;
}