DMOPC '22 Contest 3 P6 - Compressibility

View as PDF

Submit solution

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

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 s as the maximum integer k such that s is the concatenation of k copies of some string t, 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 1 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 34 while the compressibility of huffman is 29, even though they both have repeatability 1.

In order for this metric to be useful though, it remains to find an efficient algorithm that computes the compressibility of any given string S. Therefore, your job is to write a program to help him compute the compressibility of S.


1 \le |S| \le 2 \times 10^5

S only contains lowercase characters.

Subtask 1 [10%]

1 \le |S| \le 500

Subtask 2 [20%]

1 \le |S| \le 5 \times 10^3

Subtask 3 [70%]

No additional constraints.

Input Specification

The first and only line contains a string S.

Output Specification

Output the compressibility of S on its own line.

Sample Input


Sample Output


Explanation for Sample

There are 23 substrings of repeatability 1.

There are 4 substrings of repeatability 2, namely S[0:1] = \text{aa}, S[1:2] = \text{aa}, S[4:5] = \text{aa}, and S[1:6] = \text{aabaab}.

There is 1 substring of repeatability 3, namely S[0:2] = \text{aaa}.

Thus, the compressibility can be computed as 23 \times 1 + 4 \times 2 + 1 \times 3 = 34.


There are no comments at the moment.