Spotting patterns in seemingly random strings is a problem
with many applications. E.g., in our efforts to understand the
genome we investigate the structure of DNA strings. In data
compression we are interested in finding repetitions, so the
data can be represented more efficiently with pointers. Another
plausible example arises from the area of artificial
intelligence, as how to interpret information given to you in a
language you do not know. The natural thing to do in order to
decode the information message would be to look for repetitions
in it. So if the SETI project (the Search for Extra Terrestrial
Intelligence) ever get a signal in the H21-spectra, we need to
know how to decompose it.
One way of capturing the redundancy of a string is to find
its factoring. If two or more identical substrings $A$ follow each other in a string
$S$, we can represent this
aprt of $S$ as the
substring $A$, enclosed by
parentheses, raised to the power of the number of repetitions.
E.g., the string $DOODOO$
can be factored as $(DOO)^2$, but also as $(D(O)^2)^2$. Naturally, the latter
factoring is considered better since it cannot be factored any
further. We say that a factoring is irreducible if it does not
contain any consecutive repetition of a substring. A string may
have several irreducible factorings, as seen by the example
string $POPPOP$. It can be
factored as $(POP)^2$, as
well as $PO(P)^2OP$. The
first factoring has a shorter representation and motivates the
following definition. The weigh of a factoring equals
the number of characters in it, excluding the
parentheses and the exponents. Thus the weight of $(POP)^2$ is $3$, whereas $PO(P)^2OP$ has weight $5$. A maximal facotring is a
factoring with the smallest possible weight. It should be clear
that a maximal factoring is always an irreducible one, but
there may still be several maximal factorings. E.g., the
string $ABABA$ has two
maximal factorings $(AB)^2A$ and $A(BA)^2$.
Input
The input consists of a single line, containing a string of
at least one, but at most $200$ characters from the capital
alphabet A-Z.
Output
Output the weight of a maximal factoring of the input
string.
| Sample Input 1 |
Sample Output 1 |
PRATTATTATTIC
|
6
|
| Sample Input 2 |
Sample Output 2 |
GGGGGGGGG
|
1
|
| Sample Input 3 |
Sample Output 3 |
PRIME
|
5
|
| Sample Input 4 |
Sample Output 4 |
BABBABABBABBA
|
6
|
| Sample Input 5 |
Sample Output 5 |
ARPARPARPARPAR
|
5
|
