Migrated from Lutece 3274 明日を漁れ

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: KMP / Z 函数

本题面由 空気力学の詩 友情提供

月岛鸦打算在纸上印一串字符，为了完成这项工作，她决定制作一个印章。

印章每次使用时，都会将印章上的所有字符印到纸上。

同一个位置上的相同字符可以印许多次，例如用 $\texttt{aba}$ 这个印章在印制 $\texttt{ababa}$ 时，中间的 $\texttt{a}$ 就被印了两次。

但由于印上去的东西不能被擦掉，因此在同一个位置印上不同的字符是不允许的，例如用 $\texttt{abc}$ 这个印章无法完成印制 $\texttt{ababc}$ 的工作。

现在鸦想要知道在完成印制工作的前提下，对应的印章上的字符串的最小长度是多少。

Input

输入包含一个非空字符串 $S$ 代表鸦要印制的字符串。

Output

输出一个整数，代表印章上的字符串长度的最小值。

Samples

ababbababbabababbabababbababbaba

8

abbabbababbab

5

Constraints

$1\le |S|\le10^7$，$S$ 中只包含小写字母。

Note

一种印章的选择为 $\texttt{ababbaba}$，印制过程如下：

ababbababbabababbabababbababbaba
ababbaba
     ababbaba
            ababbaba
                   ababbaba
                        ababbaba

Resources

2024 UESTC ICPC Training for String