1511: [POI2006]OKR-Periods of Words
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 174 Solved: 92
[Submit][Status]
Description
一
个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串P是串A的前缀, 当且仅当存在串B, 使得 A = PB. 如果 P A
并且 P 不是一个空串,那么我们说 P 是A的一个proper前缀.
定义Q 是A的周期, 当且仅当Q是A的一个proper 前缀并且A是QQ的前缀(不一定要是proper前缀). 比如串 abab 和
ababab 都是串abababa的周期. 串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候), 比如说,
ababab的最大周期是abab. 串abc的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.
个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串P是串A的前缀, 当且仅当存在串B, 使得 A = PB. 如果 P A
并且 P 不是一个空串,那么我们说 P 是A的一个proper前缀.
定义Q 是A的周期, 当且仅当Q是A的一个proper 前缀并且A是QQ的前缀(不一定要是proper前缀). 比如串 abab 和
ababab 都是串abababa的周期. 串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候), 比如说,
ababab的最大周期是abab. 串abc的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.
Input
第一行一个整数 k ( 1 k 1 000 000) 表示串的长度. 接下来一行表示给出的串.
Output
输出一个整数表示它所有前缀的最大周期长度之和.
Sample Input
8
babababa
babababa
Sample Output
24
HINT
Source
题解:
想了一会儿发现最大周期其实就是求前缀的len--最短的前缀==后缀的len
正确性显然,然后就kmp搞定了。
代码:
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 1000000+5 #define maxm 500+100 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
int n,next[maxn];
ll ans;
char s[maxn]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();
scanf("%s",s+);
for(int i=,j=;i<=n;i++)
{
while(j&&s[j+]!=s[i])j=next[j];
if(s[j+]==s[i])j++;
next[i]=j;
}
for1(i,n)if(next[next[i]]!=)next[i]=next[next[i]];
for1(i,n)if(next[i])ans+=(ll)(i-next[i]);
printf("%lld\n",ans); return ; }