## DMOPC '22 Contest 3 P6 - Compressibility

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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 .

#### Constraints

only contains lowercase characters.

#### Input Specification

The first and only line contains a string .

#### Output Specification

Output the compressibility of on its own line.

#### Sample Input

aaabaab

#### Sample Output

34

#### 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 .