定义 \(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;
}
标签:nxt,前缀,int,POI2006,long,len,Periods,ans,P3435
From: https://www.cnblogs.com/zhouzizhe/p/16639036.html