2021.11.09 P3435 [POI2006]OKR-Periods of Words（KMP)
https://www.luogu.com.cn/problem/P3435
题意：
对于一个仅含小写字母的字符串 a，p 为 a 的前缀且 p不等于a，那么我们称 p 为 a的 proper 前缀。
规定字符串 Q（可以是空串）表示 a的周期，当且仅当 Q是 a的 proper 前缀且 a是 Q+Q 的前缀。
例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。
求给定字符串所有前缀的最大周期长度之和。
分析：
https://ofnoname.blog.luogu.org/solution-p3435
nexti数组存的是最长的 前缀与后缀 的公共前缀！
代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll ans;
int n,nexti[N];
char s[N];
int main(){
cin>>n;
scanf("%s",s);
int k=-1;
nexti[0]=-1;
for(int i=0;i<n;){
while(s[i]!=s[k]&&k!=-1)k=nexti[k];
if(s[i]==s[k]||k==-1)nexti[++i]=++k;
}
//for(int i=1;i<=n;i++)cout<<nexti[i]<<" ";cout<<endl;
for(int i=2,j=2;i<=n;i++,j=i){
while(nexti[j])j=nexti[j];
if(nexti[i])nexti[i]=j;
ans+=i-j;
}
cout<<ans;
return 0;
}
