题解 P3435 【[POI2006]OKR-Periods of Words】
oscar
2017-09-28 18:22:54
【POI补全计划#19 POI2006 OKR】
根据数据范围猜算法！这题一看就要求出next数组
接下来想一下题目里说的“周期”代表着什么——某段后缀与某段前缀相等且没有重叠部分
于是求最长周期串就等价于求最短前缀使得该前缀等于一个等长的后缀
这个信息可以通过next数组不停往前跳（直到最后一个非0位置）得到
P.S.不要忘记开long long（我就是因为这个挂了两次orz）
最后贴代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[1234567];
int fail[1234567],to[1234567];
int main()
{
int len;
scanf("%d",&len);
scanf("%s",str+1);
int k=0;
long long ans=0;
for(int i=2;i<=len;++i)
{
while(k&&str[k+1]!=str[i])k=fail[k];
if(str[k+1]==str[i])++k;
fail[i]=k;
}
for(int i=1;i<=len;++i)
{
if(fail[i])to[i]=to[fail[i]];
else to[i]=i;
ans+=i-to[i];
}
printf("%lld\n",ans);
return 0;
}
```