题目描述
给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。
输入格式
第一行一个整数 $L$，表示给出字符串的长度。
第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。
输出格式
仅一行，表示 $s_2$ 的最短长度。
样例 #1
样例输入 #1
8
cabcabca样例输出 #1
3提示
样例输入输出 1 解释
对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabc}$，读入的 $\texttt{cabcabca}$，是它的子串。
规模与约定
对于全部的测试点，保证 $0 < L \le 10^6$。
分析
我首先想到的是二分答案，但仔细想想不太可行。
样例中cab首尾相接，各不相同，next全0，而后一直增加，这大概可以从next数组考虑。于是打表找规律。
abcdabcdab
0000123456猜想大概是要找后面的123456...，而答案就是前面0的个数，因为abcd各不相同，而循环节之后next数组就应该一直增加。
但这只是循环节各不相同的简单情形，如果有相同的呢？
xbbxbbx
0001234嗯，好像也一样。那这样呢：
abaabaab
00112345事情正起变化，因为循环节本身的结构，123456...前面不全是0了，但可喜可贺这似乎不是很影响，我们只要修正已有的结论：答案是123456...前面元素的个数。这里有一个trick，其实答案就是123456...中1的位置（下标从0开始算）。
但是，有一个很讨厌的情况！
abaabaak
00112340这个时候答案是多少呢？根据题意我们只能把整个abaabaak作为循环节了，因此答案是8。这似乎只要加个特判？并非如此，因为next数组递减不一定是减到0，所以还有其他情况，结论需要大修特修。
position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
next 0 0 0 0 1 2 3 1 2 3 4 5 6 7 4 0
content a g c t a g c a g c t a g c t g上面这个例子就包含很多了。结论是令ans为next数组中第一个1的位置，在后续的扫描中若next数组递减，则更新ans=pos-next[pos]+1。
回顾之前的例子：
abaabaab
00112345为追求形式的统一，将结论进一步修正为：令ans为next数组中第一个1的位置，在后续的扫描中若next数组不增，则更新ans=pos-next[pos]+1。
这个结论的原理其实就在next数组的定义中，这里不展开。
代码
#include <cstdio>
const int MAXL = 1e6+10;
char s1[MAXL];
int mynext[MAXL], L;
void getNext(){ //前置知识点，next数组
int j = 0;
mynext[0] = 0;
for(int i=1; i<L; i++){
while(j>0 && s1[i]!=s1[j]) j=mynext[j-1];
if(s1[i]==s1[j]) j++;
mynext[i] = j;
}
}
int main(){
scanf("%d%s",&L,s1); //C风格字符串
if(L==1){printf("1");return 0;} //特判
getNext();
int pos = 0, ans = 1;
while(!mynext[pos]){
pos++;
if(pos == L){
printf("%d",L); return 0;
}//指向尾后，next全0
}
ans = pos; //此时pos指向next数组中第一个1
for(; pos<L; pos++){
if(mynext[pos] <= mynext[pos-1]){
//next数组第一个一定是0，所以不会越界
ans = pos-mynext[pos]+1;
}
}
printf("%d",ans);
return 0;
}