定义 \(Q\) 是 \(a\) 的周期表示 \(Q\) 是 \(a\) 的前缀， \(Q\neq a\) 且 \(a\) 是 \(Q+Q\) 的前缀。求给定字符串前缀的最大周期之和。 \(|S|\leq 10^6\)。
题目中对周期的定义很关键，需要推一下。以样例为例，
求bababa的最大周期：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| b | a | b | a | ||||
| b | a | b | a | b | a | ||
| b | a | b | a | b | a | b | a |
第一排是最大周期记为 \(Q\) ，第二排是原串 \(a\) ，第三排是\(QQ\)
可以发现 \(Q[1~2]=QQ[5~6]=a[5~6]\) ，即 \(Q\) （一定是自己的字串）的前缀等于 \(a\) 的后缀，想到KMP。\(ans=2 \times len(Q)-len(a)=len(Q)-\)重复部分 。
再举一例：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | c | ||||||
| a | b | c | a | b | c | a | b | ||||
| a | b | c | a | b | c | a | b | c | a | b | c |
在 \(a\) 的 \(nxt\) 数组中 \(nxt[8]=5\) ，但为了 \(ans\) 最大，重复部分要尽可能小，所以取 \(nxt[nxt[...]]\) 。注意用记忆化搜索避免时间复杂度退化。 \(ans\) 开\(long long\)
#include<bits/stdc++.h>
using namespace std;
long long ans;
int n,nxt[1000005];
char s[1000005];
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=2,j=0;i<=n;++i)
{
while(s[i]!=s[j+1] && j>0)
j=nxt[j];
if(s[i]==s[j+1])
++j;
nxt[i]=j;
}
for(int i=2,j=2;i<=n;++i,j=i)
{
while(nxt[j])
{
j=nxt[j];
}
if(nxt[i])
nxt[i]=j;
ans+=i-j;
}
printf("%lld",ans);
return 0;
}