1 // 区间DP+next求循环节 uva 6876 2 // 题意：化简字符串 并表示出来 3 // 思路：dp[i][j]表示 i到j的最小长度 4 // 分成两部分 再求一个循环节 5  6 #include <iostream> 7 #include <algorithm> 8 #include <cstring> 9 #include <cstdio>10 #include <vector>11 #include <cmath>12 #include <map>13 #include <queue>14 using namespace std;15 #define LL long long16 typedef pair<int,int> pii;17 const int inf = 0x3f3f3f3f;18 const int MOD = 998244353;19 const int N = 1020;20 const int maxx = 200010; 21 #define clc(a,b) memset(a,b,sizeof(a))22 const double eps = 0.025;23 void fre() {freopen("in.txt","r",stdin);}24 void freout() {freopen("out.txt","w",stdout);}25 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}26 27 char s[N];28 int dp[N][N];29 int cas=1;30 int nextt[N];31 32 int getnext(char *t,int len){33     int i=0,j=-1;34     // int len=strlen(t);35     nextt[0]=-1;36     while(i<len){37         if(t[i]==t[j]||j==-1){38             i++;39             j++;40             nextt[i]=j;41         }42         else43             j=nextt[j];44     }45     return len-nextt[len];46 }47 48 int getbit(int x){49     int cnt=0;50     while(x){51         x/=10;52         cnt++;53     }54     return cnt;55 }56 void DP(){57     int n=strlen(s+1);58     for(int i=1;i<=n;i++) {59         for(int j=i+1;j<=n;j++)60            dp[i][j]=1010;61         dp[i][i]=1;62     }63     for(int len=2;len<=n;len++){64         for(int l=1;l+len-1<=n;l++){65             int r=l+len-1;66             for(int k=l;k<r;k++){67                 dp[l][r]=min(dp[l][k]+dp[k+1][r],dp[l][r]);68             }69             int t=getnext(s+l,len);70             if((len%t)==0){71                 int tem=dp[l][l+t-1];72                 if(t>1) tem+=2;73                 tem+=getbit(len/t);74                 dp[l][r]=min(dp[l][r],tem);75             }76         }77     }78     printf("Case %d: %d\n",cas++,dp[1][n]);79 }80 int main(){81     // fre();82     while(~scanf("%s",s+1)){83         if(s[1]==‘0‘) break;84         DP();85     }86     return 0;87 }