2996. [POJ 2176]折叠字符串(Folding)

【题目描述】

中中正在试图用折叠重复子串的方式，紧凑地表示由大写字母 $A$ 到 $Z$ 组成的字符串。

例如，表示字符串 $AAAAAAAAAABABABCCD$ 的一种方式是 $10(A)2(BA)B2(C)D$。

他通过以下方式定义了折叠的字符串以及它们的展开变换：

$1$.包含单个字符的字符串被认为是折叠字符串，展开它得到的字符串为它本身。

$2$.如果 $S$ 和 $Q$ 是两个折叠字符串，并且 $S$ 可以展开得到 $S′$，$Q$ 可以展开得到 $Q′$，则认为 $SQ$ 也是一个折叠字符串，并且 $SQ$ 展开得到 $S′Q′$。

$3$.如果 $S$ 是折叠字符串，则 $X(S)$ 也是折叠字符串，其中 $X$ 为大于 $1$ 的整数。如果 $S$ 展开得到 $S′$，则 $X(S)$ 展开得到 $X$ 个 $S′$。

根据定义可以展开任意给出的折叠字符串，现在给出原字符串，请你将它折叠，并使得折叠字符串包含尽可能少的字符数。

【输入格式】

输入文件包含一个由 $L$ 个大写字母构成的字符串。

【输出格式】

输出文件包含字符数最少的折叠字符串，如果答案不唯一则任意输出一个即可。

【样例输入】

AAAAAAAAAABABABCCD

【样例输出】

9(A)3(AB)CCD

【数据规模与约定】

其中 $7$ 组数据，$1 \leq L \leq 5$；

其中 $16$ 组数据，$1 \leq L \leq 15$；

其中 $12$ 组数据，构成输入字符串的集合中只有 $1$ 个大写字母；

对于 $100\%$ 的数据，$1 \leq L \leq 100$；