题解 P3435 【[POI2006]OKR-Periods of Words】

# 广告 [蒟蒻のblog](http://www.cnblogs.com/dedicatus545/p/8900630.html) # 思路 先把题面转成人话： 对于给定串的每个前缀i，求最长的，使这个字符串重复两边能覆盖原前缀i的前缀（就是前缀i的一个前缀），求所有的这些“前缀的前缀”的长度和 利用$next$的性质：前缀$i$的长度为$next[i]$的前缀和后缀是相等的 这说明：如果有i一个公共前后缀长度为j，那么这个前缀i就有一个周期为i-j 见下图  显然图中蓝色线段是黑色线段的一个周期 那么接下来的问题就容易了： 先求出$next$数组 对于每个前缀$i$，令$j=i$，然后在$j>0$的情况下令$j=next[j]$，最小的$j$就是答案，此时$ans+=i-j$ 一个优化：求出$j$以后，令$j=fail[i]$，这样能加快递归速度（相当于记忆化了） # Code ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; char a[1000010];int n,fail[1000010]; int main(){ scanf("%d",&n);scanf("%s",a);int i,j;ll cnt=0; fail[0]=fail[1]=0;j=0; for(i=1;i<n;i++){//求解next while(j&&(a[i]!=a[j])) j=fail[j]; j+=(a[i]==a[j]);fail[i+1]=j; } for(i=1;i<=n;i++){ j=i; while(fail[j]) j=fail[j]; if(fail[i]!=0) fail[i]=j;//记忆化 cnt+=i-j; } printf("%lld",cnt); } ```