25227번 - 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

abcabcabcabc

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

abc[3,9]

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.

제한

힌트