Description
给定一个字符串，求其可重叠的最小循环节长度。
Analysis
思考一下，如果 $A$ 是 $B$ 的最小可重叠循环节，那么 $A$ 在 $B$ 的最初和最末位置都出现过。
假设 $A$ 只在这两个位置出现过，也就是说 $B$ 此时是由 $\le 2\times|A|$ 个字符组成的。这时的 $A$ 可以通过 KMP 直接求得。
如果我们再在 $B$ 后加上一段新的字符，使得 $A$ 出现了三次，但是 $A$ 仍然是 $B$ 的最小可重叠循环节。
这时的 $A$ 虽然无法直接求得，但是修改后对答案无影响。
反过来说，如果是三个 $A$ 组成了 $B$，我们在 $B$ 后删除一段字符使得 $B$ 只由两个 $A$ 组成，就可以 KMP直接求，且答案不会改变。
说明什么？我们的答案是从前面的状态推到了后面的状态，且前面的状态可以由 KMP 求出来。
接下来我们考虑递推的状态是什么。
Solution
我们设给出的字符串为 $S$，长度为 $n$。设 $f[i]$ 表示 $S[1\dots i]$ 这一段的答案。
首先有一个结论：$f[i]$ 只能是 $i$ 或者 $f[nxt[i]]$。
证明：
首先有两个显然结论：
$f[i]$ 一定 $\le i$，因为最劣情况下，它可以自己覆盖自己。
$f[nxt[i]]\le f[i]$，因为 $nxt[i]\le i$，它覆盖区间更短，所以它不可能更大。
剩下的考虑反证法。
若 $f[i]<f[nxt[i]]$，则说明 $f[i]$ 无法覆盖 $S[1\dots nxt[i]]$，那么它显然也无法覆盖 $S[1\dots i]$，所以不成立。
并且 $i>nxt[i]$，$f[nxt[i]]$ 能覆盖 $S[1\dots nxt[i]]$，所以 $f[nxt[i]]$ 应该要更小。
若 $f[nxt[i]]<f[i]<i$，则说明最长公共前后缀长度是 $f[i]$。但是根据 KMP 原理，$nxt[i]$ 才是最长公共前后缀长度。
又因为 $f[nxt[i]]\le nxt[i]$，所以 $f[i]>nxt[i]$，所以不成立。
综上，$f[i]$ 只能是 $i$ 或者 $f[nxt[i]]$。
接下来考虑什么情况下可以确定它的具体取值。
$f[i]=f[nxt[i]]$ 的充要条件是 $j\in[i-nxt[i],i)$ 且 $f[j]=f[nxt[i]]$。
因为 $f[nxt[i]]$ 可以覆盖前 $nxt[i]$ 个字符，所以也可以覆盖后 $nxt[i]$ 个字符。并且 $f[j]$ 可以覆盖 $S[1\dots j]$。
若 $f[j]\ne f[nxt[i]]$，那么它连 $S[1\dots nxt[i]]$ 都无法覆盖。
若 $f[j]\notin [i-nxt[i],i)$，则至少有 $S[j+1\dots i-nxt[i]]$ 这一段不会被覆盖。
所以判断一下存不存在一个答案是 $f[nxt[i]]$ 的值存在于 $[i-nxt[i],i)$ 即可。
当然，还有一种情况：如果给出的字符串只包含一种字符，那么上面都是扯淡，直接输出 $1$ 即可。
Code
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 500010
#define INF 0x3f3f3f3f
//#define int long long
char s[maxn];
bool flag;
int n,ans,Fir,Sec;
int Nxt[maxn],f[maxn],pre[maxn];
//f[i] 表示 1 到 i 这段区间的最佳答案；
//pre[i] 表示答案 i 出现的最新位置，也就是说 pre[f[i]] 就是 f[i] 这个答案出现的最新位置qwq；
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(int i=2;i<=n;i++) if(s[i]!=s[1]) flag=true;
if(!flag){printf("1\n");return 0;}
for(int i=2;i<=n;i++){
while(Fir&&s[Fir+1]!=s[i]) Fir=Nxt[Fir];
if(s[Fir+1]==s[i]) Fir++;Nxt[i]=Fir;
}
for(int i=2;i<=n;i++){
f[i]=i;
if(pre[f[Nxt[i]]]>=i-Nxt[i]) f[i]=f[Nxt[i]];
pre[f[i]]=i;
}
printf("%d",f[n]);
return 0;
}
