← 返回题目列表

Codeforces · 825/F

F. 字符串压缩

中文机器翻译题面 查看原题

伊万想给他的朋友写一封信。该字母是由小写拉丁字母组成的字符串 s。

不幸的是,当伊万开始写这封信时,他意识到这封信很长,写整封信可能需要非常长的时间。所以他想写字符串 s 的压缩版本而不是字符串本身。

字符串 s 的压缩版本是字符串 c1、s1、c2、s2、...、ck、sk 的序列,其中 ci 是数字 ai 的十进制表示形式(不带任何前导零),si 是由小写拉丁字母组成的字符串。如果 Ivan 将字符串 s1 精确写入 a1 次,然后将字符串 s2 精确写入 a2 次,依此类推,结果将是字符串 s。

压缩版本的长度为 |c1| + |s1| + |c2| + |s2|... |ck| + |sk|。在所有压缩版本中,Ivan 希望选择一个长度尽可能最小的版本。帮助 Ivan 确定可能的最小长度。

输入

输入的唯一一行包含一个由小写拉丁字母组成的字符串 s (1 ≤ |s| ≤ 8000)。

输出

输出一个整数 — s 的压缩版本的最小可能长度。

示例

输入 #1

aaaaaaaaaa

输出 #1

3

输入 #2

abcab

输出 #2

6

输入 #3

cczabababab

输出 #3

7

注意

在第一个示例中,Ivan 将选择此压缩版本:c1 是 10,s1 是 a。

在第二个示例中,Ivan 将选择此压缩版本:c1 为 1,s1 为 abcab。

在第三个示例中,Ivan 将选择此压缩版本:c1 为 2,s1 为 c,c2 为 1,s2 为 z,c3 为 4,s3 为 ab。