题目描述
Problem Description
Given a string consisting of lowercase letters, we can use a simple method to compress the repetitive information within it. The compressed string can include, but is not required to, uppercase letters R and M, where M marks the start of a repeated sequence, and R repeats the decompressed result (referred to as the buffer string) starting from the last M (or from the beginning of the string if there is no M to the left of the current position).
For example, bcdcdcdcd can be compressed to bMcdRR. The decompression process is as follows:
| Decompressed Part | Decompression Result | Buffer String |
|---|---|---|
| b | b | b |
| bM | b | . |
| bMc | bc | c |
| bMcd | bcd | cd |
| bMcdR | bcdcd | cdcd |
| bMcdRR | bcdcdcdcd | cdcdcdcd |
Input Format
The input consists of a single line containing the string to be compressed, which only includes lowercase letters, with a length of n.
Output Format
The output should be a single line, representing the shortest length of the compressed string.
Sample Input and Output
Sample Input #1
aaaaaaa
Sample Output #1
5
Sample Input #2
bcdcdcdcdxcdcdcdcd
Sample Output #2
12
Notes
In the first example, the solution is aaaRa, and in the second example, the solution is bMcdRRxMcdRR.
Constraints:
- 50% of the test cases satisfy: 1 ≤ n ≤ 20
- 100% of the test cases satisfy: 1 ≤ n ≤ 50
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分