【AtCoder Regular Contest 060 F】Best Representation | Mrsrz's blog

KMP，分类讨论。

题目大意：

给定一个长度为 $n$ 的字符串，要求将其分为最少的 $k$ 段，使得每段的子串都不能通过另一个比它更小的串重复得到。

比如 ababab 就可以由 ab 重复得到。

输出最小的 $k$ 以及在这个 $k$ 下的分割方案数。

题解：

对原串进行 KMP，求出 fail 数组。

然后一个串的最小循环节的长度，就是 $n-fail_n$。这里的循环节，在最后一位可能不满。

如果最后一位不满（$n$ 不能被 $n-fail_n$ 整除）或 $fail_n=0$，则原串本身划分为一段就是合法方案，方案数为 $1$。

如果最后一位也能满，则说明确实存在完整的循环。这里分循环节长度为 $1$ 和不为 $1$ 进行讨论。

若循环节长度为 $1$，说明整个串都是同一个字符，那么必须划分为 $n$ 个段才能满足条件。方案数为 $1$。

若循环节长度不为 $1$，则必定存在划分成 $2$ 个段的方案（比如把最后一个字符单独划分为一段）。考虑求此时的方案数。

我们枚举断点的位置，这个位置将字符串划分为一个前缀和后缀。我们利用 KMP 得到的每个前缀的 fail 数组即可计算这个前缀是否存在完整的循环节。后缀同理。如果一个断点的前缀、后缀都不存在循环节，则这个断点合法。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
#include<algorithm>
#include<cstring>
const int N=5e5+5;
int fail[N],n,t;
int vis[N];
char s[N];
void getfail(){
    for(int i=2,j=0;s[i];++i){
        while(j&&s[j+1]!=s[i])j=fail[j];
        if(s[j+1]==s[i])++j;
        fail[i]=j;
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    getfail();
    if(n%(n-fail[n])!=0||!fail[n])puts("1\n1");else
    if(fail[n]==n-1)printf("%d\n1\n",n);else{
        for(int i=1;i<=n;++i)vis[i]=i%(i-fail[i])==0&&fail[i];
        std::reverse(s+1,s+n+1);
        getfail();
        for(int i=1;i<=n;++i)vis[n-i]|=i%(i-fail[i])==0&&fail[i];
        for(int i=1;i<=n;++i)t+=!vis[i];
        printf("2\n%d\n",t);
    }
    return 0;
}