AT2040 [ARC060D] 最良表現 / Best Representation

SSER_ZRQ · 2022-08-04 21:44:44 · 题解

题目翻译：

• 称一个串 S 是优的当且仅当它不能被切割成若干个相等的串 s。
• 称一个串 T 的最优表达是指把 T 切割成最少的串 \{S_1,S_2,...S_k\}，使得每个串 S_i 都是优的。
• 给定串 T ，求：
• 最优表达含多少个串；
• 最优表达有多少种。

题解

设串 T 长度为 n .

首先，如果串 T 只由一个字母组成，那么只能分成 n 段。

其次，如果 T 没有循环节，则最优表达只含一个串，即串 T 本身。

对于其他情况，最优表达一定只有 2 个串，然后枚举 n-1 个可能的断开处，通过 kmp 检查下前缀后缀是否有循环节即可,如果没有，方案+1。

kmp 关于循环节的结论：如果 i \bmod (i-nex_i) = 0，那么 i-nex_i 是前缀 i 的一个循环节。
事实上，i-nex_i 总是前缀 i 的一个周期

用 O(n) 时间求出正序（判断前缀）和倒序（判断后缀）kmp，然后用 O(n) 求和。

贴上代码：

#include<bits/stdc++.h>
using namespace std;
#define N 500005
int n,p[N],f[N],ans,v[N];
char s[N],c[N];
int teshu(){
    v[s[1]]++;
    for(int i=2;i<=n;i++){
        if(!v[s[i]]) return 0;
    }
    return 1;
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    if(teshu()){
        printf("%d\n1",n);
        return 0;
    }//判断特殊情况 
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j=p[j];
        if(s[i]==s[j+1]) j++;
        p[i]=j;
    }
    for(int i=1;i<=n;i++) c[i]=s[n-i+1];
    //逆转序列，求倒序kmp 
    for(int i=2,j=0;i<=n;i++){
        while(j&&c[i]!=c[j+1]) j=f[j];
        if(c[i]==c[j+1]) j++;
        f[i]=j;
    }
    if(p[n]==0||n%(n-p[n])!=0){
        printf("1\n1");
        return 0;
    }//情况2，本身就是答案 
    for(int i=1;i<n;i++){ 
        if((p[i]==0||i%(i-p[i])!=0)&&(f[n-i]==0||(n-i)%(n-i-f[n-i])!=0))
            ans++;
        //注意下标问题 
    }
    printf("2\n%d\n",ans);
    return 0;
}