H. *【KMP】字符串最小周期[BalticOI 2009]Radio Transmission

传统题

1000ms

512MiB

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

【题意】

给出一个长字符串 $S$ ，要求找到一个短字符串 $s$ ，使得 $S$ 是 $s^x(x \ge 1)$ 的子串，求 $s$ 的最短长度。

第一行一个整数，表示 $|S| \ (1\le |S| \le 10^6)$ 。

第二行一个字符串 $S$ ，全由小写字母组成。

输出最短的长度。

8
cabcabca

对于样例，我们可以利用 cab 不断自我连接得到 cabcabcab，读入的 cabcabca 是它的子串。