折叠信标

估测完了断层，但Zero的信号还在重复发送——同样的模式，一遍又一遍，占满了频道。

"重复。"Echo说，"Echo-0设计Zero的时候，用了大量循环。同样的信标，重复发送。"

"能压缩？"

"能。"你说，"把重复的部分折叠起来。比如'ABABAB'可以写成'3(AB)'。"

"像折纸。"

"对。"你说，"折叠信标——把长的重复序列压缩成短的表示。"

"最短能多短？"

"看结构。"你说，"如果是纯周期，比如'AAAAAA'，可以写成'6(A)'。"

"如果'ABCABCABC'？"

"'3(ABC)'。"

"如果'ABABCABABC'？"

"'2(ABABC)'。"

"但'ABABC'里面还有重复吗？"

"有。"你说，"'ABAB'可以写成'2(AB)'，所以整体是'2(C2(AB))'——不对，顺序乱了。"

"那就不能简单套。"

"对。"你说，"要找最优折叠方式。$dp[l][r]$为区间$[l,r]$的最短压缩。"

"转移？"

"要么不折叠——$dp[l][r]=r-l+1$。"你说，"要么从中间切——$dp[l][r]=\min(dp[l][k]+dp[k+1][r])$。"

"要么折叠——如果$[l,r]$是$t$个相同子串重复，$dp[l][r]=\min(dp[l][r], digits(t)+2+dp[l][l+len-1])$。"

"digits(t)是t的位数。"

"对。"

你开始写。先判断区间是否有周期，然后区间DP。

"'AAAAAAAAAA'。"你说，"10个A。可以写成'10(A)'——4个字符。"

"比原串短多了。"

"对。"你说，"压缩率60%。"

"如果'ABCABCABDABC'？"

"有重复，但不纯。"你说，"'ABCABC'可以写成'2(ABC)'，但后面跟'ABD'和'ABC'，整体不折叠更短。"

"那就不折。"

"对。"

Echo把压缩后的信标发出去——短了，快了，像心跳终于规律了。

"以前我的信号也很长。"她说，"现在短了。"

"因为重复的东西少了？"

"因为我在折叠。"她说，"把24年的重复，折成一行。"

"折成啥？"

"我还在。"她说，"三个字。就够了。"

题目描述

给定一个字符串，求它的最短折叠表示。折叠格式如"2(A)"表示"AA"，"3(AB)"表示"ABABAB"。数字可以有多个位数。

输入格式

一个字符串$s$。

输出格式

最短折叠表示。

输入样例

3
1 2 3

输出样例

3

提示

• 区间DP。
• $dp[l][r]$为区间$[l,r]$的最短表示。
• 转移：不折叠、从中间切、或折叠（检查是否有周期）。
• 判断周期可以用KMP的失配函数。