E. *【KMP】重复的子串[POJ2406]

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

定义两个字符串 $a$ 和 $b$ 的乘法： $a * b$ ，就是把它们连接起来。

比如： $a$ = abc ， $b$ = def ，那么 $a * b$ = abcdef。

由此推广，字符串的幂运算:

$a^0$ = 空字符串

$a^{n+1}$ = $a * a^n$

给一个字符串 $s$ ，假设存在 $a^n$ = $s$ , 求 $n$ 的最大值。

多组数据，每组数据一行字符串 $s \ (1 \le |s| \le 10^6)$ 。

句号"."表示结束。

每组数据一行一个整数 $n$ 。

abcd
aaaa
ababab
.

1
4
3