题解 P3435 【[POI2006]OKR-Periods of Words】
RPChe_
2020-07-31 17:11:27
让窝来贡献一个$O(n\log n)$算法。~~讲解很详细哦~~
****************************
联系kmp算法中的next数组和题目中提到的周期，我们可以发现一个结论：一个字符串的最大周期长度就是这个字符串的长度减去它最短的公共前后缀长度，而且这个公共前后缀的长度必须小于等于字符串长度的一半，否则不存在周期。
举个简单的例子，假设我们要求串$S$的某个周期长度，且这个串存在一个小于其长度一半的公共前后缀T，如下：
因为$ab$段与$cd$段一样，我们可以把$ac$段子串向右移动到$a$点与$c$点重合，这样就得到了如下一个新串$ae$：
在这个新串中，$ac$与$ce$对应，$ab$与$cd$对应，$bc$与$de$对应，那么我们可以发现，$ac$的长度就是这个周期的长度，因为$ac$是$S$的前缀，且$S$是$ac$+$ac$，即$ae$的前缀。所以接下来我们要使得这个$ac$的长度尽量长，就是$cd$的长度尽量短，那么问题就转化为了求取$S$的最短公共前后缀长度。
这个很好办，我们只需要不断往前跳next数组寻找合法解就好了。
注意到以上的论述建立在一个前提上：$ab$的长度小于等于$S$的一半，所以这个最短公共前后缀的长度还必须小于等于字符串长度的一半，否则无解。
接下来就是代码实现了。我一开始就暴力跳next数组，结果TLE了几个点。但是窝太菜了，根本没有想到记忆化，而是想到了一个非常优雅的暴力——倍增。
如果不知道倍增，可以去研究一下倍增求LCA的算法，这里不再赘述。
于是我们便得到了以下代码——
```cpp
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define maxn 1000005
using namespace std;
int len,nxt[maxn],f[maxn][21];
long long ans;
string s;
void kmp() {
nxt[0]=-1;
f[1][0]=0;
int j=-1;
rep(i,0,len-1) {
while(j>-1&&s[j+1]!=s[i+1]) j=nxt[j];
if(s[j+1]==s[i+1]) j++;
nxt[i+1]=j;
f[i+2][0]=j+1;//因为倍增数组涉及到以字符的位置作下标，为了方便处理，我们把字符的位置加1
}
}//kmp模板
void pretreat() {
rep(i,0,len-1) {
rep(j,1,20) {
f[i+1][j]=f[f[i+1][j-1]][j-1];
}
}
}//预处理出倍增数组
void check() {
rep(i,0,len-1) {
int x=i+1;
for(register int j=20;j>=0;j--) {
if(f[x][j]) {
x=f[x][j];
}
}
if(i+1==x||x>i+1>>1) continue;//判断解是否合法
ans+=(long long)(i+1)-x;//更新答案
}
}//倍增找到最短公共前后缀长度
int main() {
ios::sync_with_stdio(false);
cin>>len;
cin>>s;
kmp();
pretreat();
check();
cout<<ans;
return 0;
}
```