#include <bits/stdc++.h>
#include <unistd.h>
#define init(a,b) memset(a,b,sizeof(a));
typedef long long ll;
typedef double db;
typedef long double ldb;
using namespace std;
const ll MAXN=105;
string str;
ll dp[MAXN][MAXN],c[MAXN][MAXN],f[MAXN][MAXN];
ll calc(ll x){
	ll ans=0;
	while(x){
		x/=10;
		++ans;
	}
	return ans;
}
void check(ll l,ll r,ll k){
	if((r-l+1)%k!=0){
		return;
	}
	for(ll i=l;i+k<=r;++i){
		if(str[i]!=str[i+k]){
			return;
		}
	}
	ll t=2+calc((r-l+1)/k)+dp[l][l+k-1];
	if(t<dp[l][r]){
		dp[l][r]=t;
		c[l][r]=0;
		f[l][r]=k;
	}
}
void dfs(ll l,ll r){
	if(!c[l][r]&&!f[l][r]){
		for(ll i=l;i<=r;++i){
			cout<<str[i];
		}
	}else if(c[l][r]){
		dfs(l,c[l][r]);
		dfs(c[l][r]+1,r);
	}else{
		cout<<(r-l+1)/f[l][r]<<"(";
		dfs(l,l+f[l][r]-1);
		cout<<")";
	}
}
int main() {
	cin>>str;
	ll n=str.size();
	str=" "+str;
	init(dp,0x7f);
	init(c,0);
	init(f,0);
	for(ll i=1;i<=n;++i){
		dp[i][i]=1;
	}
	for(ll len=2;len<=n;++len){
		for(ll i=1;i+len-1<=n;++i){
			ll j=i+len-1;
			for(ll k=1;k<=(j-i+1)/2;++k){
				check(i,j,k);
			}
			for(ll k=i;k<j;++k){
				if(dp[i][j]>dp[i][k]+dp[k+1][j]){
					dp[i][j]=dp[i][k]+dp[k+1][j];
					c[i][j]=k;
					f[i][j]=0;
				}
			}
		}
	}
	dfs(1,n);
	cout<<endl;
	return 0;
}

评测记录