折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S ? S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) ? SSSS…S(X个S)。 3. 如果A ? A’, B?B’，则AB ? A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) ? AAACBB，而2(3(A)C)2(B)?AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

仅一行，即字符串S，长度保证不超过100。

仅一行，即最短的折叠长度。

一个最短的折叠为：2(NEERC3(YES))

#include<iostream>#include<cstring>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;char S[110];int f[110][110],N;#define base 13#define ULL unsigned long longULL bin[110],hash[110];void Hashtable(){    bin[0]=1; for (int i=1; i<=N; i++) bin[i]=bin[i-1]*base;    for (int i=1; i<=N; i++) hash[i]=hash[i-1]*base+S[i];}inline ULL Gethash(int l,int r) {return hash[r]-hash[l-1]*bin[r-l+1];}inline int size(int x) {int re=0; while (x) x/=10,re++; return re;}inline bool judge(int l,int m,int r){    if ((r-l+1)%m) return 0;    int tl=(r-l+1)/m; ULL t=Gethash(l,l+tl-1);    for (int i=l; i<=r; i+=tl)        if (Gethash(i,i+tl-1)!=t) return 0;    return 1;}int main(){    scanf("%s",S+1); N=strlen(S+1);    Hashtable();    for (int i=1; i<=N; i++)        for (int j=1; j<=N; j++)            if (j+i-1<=N)                {                    int l=j,r=j+i-1;                    f[l][r]=r-l+1;                    for (int k=1; k<=i; k++)                        {                            f[l][r]=min(f[l][r],f[l][l+k-1]+f[l+k][r]);                            if (judge(l,k,r)) f[l][r]=min(f[l][r],2+size(k)+f[l][l+(r-l+1)/k-1]);                        }                }    printf("%d\n",f[1][N]);    return 0;}