Description

【题目描述】

　　给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.

【输入】

　　第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.

【输出】

　　输出最短的长度

　　

题解：

首先，我们对这个字符串求一遍nextnext数组，next[i]next[i]表示i的前缀和后缀的最长的相同的长度，即最长前缀后缀。答案就是n−next[n]n−next[n]。但是为什么呢？

证明：

不妨设文本串为T，n=|T|n=|T|

下面我要证明T−next[n]T−next[n]一定是字符串的循环节。

我们把next[n]next[n]和TT这两个字符串对齐。

此时相同位置的字符是相同的。

显然，标红位置，即T−next[n]T−next[n]和next[n]next[n]的开头是相同的。

再可以把next[n]next[n]的标红部分对应回TT上面，又对应到next[n]next[n]上面。

我们可以像这样把TT和next[n]next[n]用T−next[n]T−next[n]填充满，所以T−next[n]T−next[n]一定是字符串的循环节。

那为什么T−next[n]T−next[n]一定是最短的呢？

因为如果存在比T−next[n]T−next[n]更短的循环节，根据nextnext数组的定义，next[n]next[n]一定会加长。所以不存在比T−next[n]T−next[n]更短的循环节。

因此T−next[n]T−next[n]一定是T的最短循环节，n−next[n]n−next[n]就是这个循环节的长度。

代码：

#include
    
     int n,next[1000005];char s[1000005];int main(){    scanf("%d%s",&n,s);    next[0]=next[1]=0;    for(int i=1;i