P4302 [SCOI2003] String Folding

The definition of folding is as follows: 1. A string can be considered its own folding. Denoted as `S = S`. 2. `X(S)` is the folding of the string formed by concatenating $X$ copies of `S`. Denoted as `X(S) = SSSS…S`. 3. If `A = A'`, `B = B'`, then `AB = A'B'`. For example: since `3(A) = AAA`, `2(B) = BB`, we have `3(A)C2(B) = AAACBB`, and `2(3(A)C)2(B) = AAACAAACBB`. Given a string, find its shortest folding. For example, the shortest folding of `AAAAAAAAAABABABCCD` is `9(A)3(AB)CCD`.

A single line containing the string `S`, whose length does not exceed $100$.

A single line containing the length of the shortest folding.

One shortest folding is `2(NEERC3(YES))`. It is guaranteed that for $100 \%$ of the testdata, the string `S` consists only of uppercase letters. Translated by ChatGPT 5