Згортка

Білл намагається компактно представити послідовності, що складаються з великих латинських літер від A до Z, стискаючи повторювані підпослідовності в межах них. Наприклад, одним зі способів представити послідовність AAAAAAAAAABABABCCD є 10(A)2(BA)B2(C)D. Він формально визначає згорнуті послідовності символів разом із відповідним перетворенням розгортки наступним чином:

• Послідовність, яка містить один символ від A до Z, вважається згорнутою послідовністю. Розгортання такої послідовності дає той самий символ.

• Якщо S та Q є згорнутими послідовностями, то SQ також є згорнутою послідовністю. Розгортання S до S', а Q до Q' означає, що розгортання SQ дає S'Q'.

• Якщо S є згорнутою послідовністю, то вираз X(S) також є згорнутою послідовністю, де X — це десятковий запис цілого числа, більшого за $1$. Якщо S розгортається в S', то X(S) розгортається у S', повторену X разів.

Згідно з цим визначенням, розгорнути будь-яку згорнуту послідовність досить просто. Однак Білла більше цікавить зворотне перетворення. Він хоче згорнути задану послідовність так, щоб отримана згорнута послідовність містила мінімально можливу кількість символів.