Problem C

You want to compress a given text passage using backreferences. A backreference is a pair of numbers $[a,b]$ indicating that the next $b$ characters of the string are the same as the $b$ characters starting $a$ characters back from the current position. The two strings may overlap, i.e., $a$ may be smaller than $b$.

Each backreference costs three bytes to encode, regardless of the number of characters represented by the backreference. String characters cost one byte each to encode.

For instance, the string


has 12 characters. But the last nine can be represented as a backreference to the first nine, as follows:


The total cost of this encoded string is $6$: $3$ bytes for the string abc, and $3$ bytes for the backreference.

Output the minimum cost to encode the text passage.


The single line of input contains a string $s$, with $1 \le |s| \le 10^5$. This line of text consists of upper-case letters (‘A’–‘Z’), lower-case letters (‘a’–‘z’), and spaces. There will not be any spaces at the beginning or end of the line, and no space character will be adjacent to another space character.


Output a single integer, which is the minimum cost to represent the input string using backreferences.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
Sample Input 3 Sample Output 3
A man a plan a canal Panama
CPU Time limit 1 second
Memory limit 2048 MB
Source 2022 ICPC North America Championship
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in