Problem O
Cram
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.
Input
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
Output a single integer, which is the minimum cost to represent the input string using backreferences.
| Sample Input 1 | Sample Output 1 |
|---|---|
abcabcabcabc |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
A man a plan a canal Panama |
25 |
