I Copa UHEnded |
Pepe ha estado usando últimamente el compactador que Fito creó ( TextCompact ). El algoritmo inventado por Fito aprovecha al máximo los patrones que se repiten en un texto . Si su algoritmo se encuentra la cadena 'abcabcabc ' entonces lo representa como ‘ (abc)3 ’. Si TextCompact se encuentra el texto ' axyxyxyxyb ’, lo reescribe como ‘ a(xy)4b' y adicionalmente, patrones anidados pueden ser aprovechados como el siguiente ejemplo:
Luego de pensarlo un poco, Pepe ha decidido contratarte para que implementes desde cero el algoritmo de compresión de Fito. En otras palabras, dado una cadena S, usted debe representarla con la menor cantidad de caracteres, incluyendo los paréntesis y los dígitos.
Línea 1 : Una cadena $S$ de longitud a lo sumo 1000 ($|S|$, conteniendo solamente letras en minúscula del alfabeto inglés $(a, b, …, z)$.
Línea 1 : El resultado de comprimir $S$. Note que la solución no necesariamente es única.
Hint
Note que TextCompact produce el menor texto posible (incluyendo los paréntesis y dígitos). Para el ejemplo, el texto original contiene 16 caracteres y el resultado de comprimirlo 12.