题目描述

给你一个字符串 s1，它是由某个字符串 s2 不断自我连接形成的（保证至少重复 2 次）。但是字符串 s2 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 L（1≤L≤10^6），表示给出字符串的长度。 第二行给出字符串 s1 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 s2 的最短长度。

样例

输入样例 1

8
cabcabca

输出样例 1

3

输入样例 2

10
ababababab

输出样例 2

2

输入样例 3

12
aaaaaaaabbbb

输出样例 3

12

提示

样例解析：对于样例，我们可以利用 abc 不断自我连接得到 abcabcabcabc，读入的 cabcabca，是它的子串。

思路：题意很简单，在一个字符串中找出最小周期(的长度)。 一个字符串ababababab，ab就是一个周期 但这个周期在开头和结尾不一定是完整的，例如 字符串：a[bcabcabcab]c (输入的是子串：方括号内的部分) 周期：abc 周期判定是前缀函数（next数组）的最重要应用。 一个长度为 n 的字符串的周期长度 = n - next[n-1]。(下标从0开始)