大样例下载

题目描述

有一些字符串很长，这样很占用存储空间，于是小明发明了一种新型字符串表示法，试图缩短字符串的长度。

小明在他的新型表示法中引入了两个特殊符号 @ 和 $，其中 @ 用来打标记，$ 则代表一个字符串，表示上一个 @ 的位置之后（如果之前没有 @ 则从字符串开头开始）至当前 $ 的位置之前的字符串。注意：每次的 $ 可能代表不同的字符串。

例如：字符串 abcabcbcbcbc ，长度为 12。

采用小明的表示法，该字符串可以表示为 abc$bcbcbc，该表示下的字符串长度为 10，比原字符串表示的长度缩小了。

当然，该字符串也可以表示为 abc$@bc$bc，该表示下的字符串长度为 10，并没有进一步缩短字符串的长度。

另外，该字符串还可以表示为 abca@bc$$，此时长度为 9，长度更小了。这里第一个 $ 代表字符串 bc，第二个 $ 则代表字符串 bcbcbcbc。

此外，还可以有多种表示。

我们把所有表示中（包含原始字符串），长度最短的那个表示，称为 最好表示。

字符串 abcabcbcbcbc 的最好表示就是 abca@bc$$，长度为 9.

现在给你一个字符串 S，请你求出它的 最好表示 的长度。

输入格式

一行，一个字符串 S，全部由英文小写字母构成。

输出格式

一个整数，表示 S 的最好表示的长度

样例1输入

abcabcbcbcbc

样例1输出

9

样例1解释

该样例即为题目描述中的例子。

样例2输入

aaaaaaaaaaaaa

样例2输出

6

样例2解释

最好表示为 aaa$$a

数据范围

50%的数据满足：1 ≤ |S| ≤ 20

100%的数据满足：1 ≤ |S| ≤ 50