[文章目录]
Description
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.字符串的长度,1 < L ≤ 1,000,000.
自己YY了好久，感觉跟nxt有关，最后发现答案就是长度-整个串的最长前缀后缀的长度。显然可以证明。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int len;
char s[1001000];
int nxt[1001000];
inline void get_nxt()
{
nxt[0]=-1; int k=-1,i=0;
while(i<len)
{
if(k==-1||s[i]==s[k]) i++,k++,nxt[i]=k;
else k=nxt[k];
}
}
int main()
{
scanf("%d%s",&len,s);
get_nxt();
printf("%d",len-nxt[len]);
return 0;
}