Martian DNA Formula
Time limit2sMemory limit128 MB
Compress a DNA string into the shortest possible run-length style notation using nested parentheses with repeat counts.
- Level
Hard8 of 10
- Topics
- Dynamic programming, String, String matching
- Solved
- No attempts yet
Problem
Person A has discovered the DNA formula of Martians.
A wants to give this information to B in exchange for a large amount of peanuts. Since they suspect that an organization trying to stop the formula from spreading may be listening, they decide to meet in a deserted bakery and exchange the goods there.
The formula is very long, so A wants to write it as briefly as possible before handing it over. The shortening rule is as follows.
The formula is a string consisting only of lowercase English letters. If a string is repeated several times, the repeated part may be written inside parentheses followed by the number of repetitions. For example, abcabcabc can be written as (abc)3, and axyxyxyxyb can be written as a(xy)4b. Shortenings may also be nested, so mnmndefmnmndef can be written as ((mn)2def)2.
The length of a written formula is the total number of characters, including parentheses and digits.
Given a formula, output a shortened form whose written length is as small as possible.
The optimal form does not have to be unique.
Input
The input consists of one line containing the DNA formula. The formula has length at most 1000.
Output
Output one line containing the shortest way to write the formula. If there is more than one expression with minimum length, output any one of them.