In his latest 15-122 (Principles of Imperative Computation) homework, Edward learned how to compress strings using prefix-free codes generated by Huffman coding. Although this is a great start, he wonders whether better compression algorithms exist by abusing repetitions in the string. For example, if we define the repeatability of a string as the maximum integer such that is the concatenation of copies of some string , then it is not hard to see that strings with higher repeatability are easier to compress.
However, using repeatability as a measure of compressibility is not quite perfect: the string
aaabaab only has repeatability but still contains many repetitions. In an attempt to fix this flaw, he defines the compressibility of a string as the sum of the repeatability of all of its substrings. This seems to be a better metric: the compressibility of
aaabaab is while the compressibility of
huffman is , even though they both have repeatability .
In order for this metric to be useful though, it remains to find an efficient algorithm that computes the compressibility of any given string . Therefore, your job is to write a program to help him compute the compressibility of .
only contains lowercase characters.
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
No additional constraints.
The first and only line contains a string .
Output the compressibility of on its own line.
Explanation for Sample
There are substrings of repeatability .
There are substrings of repeatability , namely , , , and .
There is substring of repeatability , namely .
Thus, the compressibility can be computed as .