【UVA11022】String Factoring

· · 题解

传送门

这个和 【SCOI2003】字符串折叠还有 【SCOI2007】压缩，完全就是一类套路题。这个应该是这三道题中最简单的一道。这里给一个稳定 O(n^3) 的区间DP做法。

设 f(i,j) 是 S[i...j] 的最优解。如果不是把 S[i...j] 整个压缩那就枚举断点 k 拆分区间。唯一需要考虑的就是压缩整个 S[i...j]

字符串的循环节是一个经典的问题，有一个很经典的性质（这里的循环节都是没有剩余）：

整除不必讲了，而这两个前缀和后缀都是由 \frac{|S|}{len} 个循环节构成，所以一定相同。而其充分性也显然成立。这其实是一个KMP的模板题，详细分析参见：这个 以及 这个。

定义 next(i,j)(i<=j) 是 S[i...j] 的最长公共前后缀。next 数组的计算就是跑 |S| 遍 kmp，可以在 O(n^2) 的时间内求出。然后我们区间DP的时候令 v=next(i,j)，可能的循环节就为 j-i+1-v，然后暴力跳转 v=next(i,v) 直到 v=0 为止。每个成立的循环节得出的答案取最小值，就是对 S[i...j] 直接进行压缩的最小答案。

虽然kmp跳转的复杂度不好算，但就算每次减1，那复杂度依旧是 O(n^3) 的，同时这个解法常数非常小所以我觉得甚至可以通过 |S|>=500 的数据qwq

代码非常简短：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define next Cry_For_theMoon
using namespace std;
const int MAXN=110;
char str[MAXN];
int n,next[MAXN][MAXN],f[MAXN][MAXN];
int main(){
    while(1){
        memset(str,0,sizeof str);
        memset(next,0,sizeof next);
        scanf("%s",str+1);
        if(str[1]=='*')return 0;
        n=strlen(str+1);
        for(int i=1;i<=n;i++){
            next[i][i]=0;
            for(int j=i+1,v=0;j<=n;j++){
                while(v && str[j] != str[i+v])v=next[i][v];
                if(str[j]==str[i+v])v++;
                next[i][j]=v;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                f[i][j]=j-i+1;
            }
        }
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                //[i,j]
                int v=next[i][j];
                while(v){
                    if(len%(len-v)==0){
                        f[i][j]=min(f[i][j],f[i][i+len-v-1]);
                    }       
                    v=next[i][v];           
                } 
                for(int k=i;k<j;k++){
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
                }
            }
        }
        printf("%d\n",f[1][n]);
    }
    return 0;
}