# P3435 [POI2006]OKR-Periods of Words

2018/08/07 16:09

## 题目描述

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn't have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

reads from the standard input the string's length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

## 输入输出格式

In the first line of the standard input there is one integer kkk ( 1≤k≤1 000 0001\le k\le 1\ 000\ 0001k1 000 000 ) - the length of the string. In the following line a sequence of exactly kkk lower-case letters of the English alphabet is written - the string.

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

## 输入输出样例

8
babababa

24

Solution:

本题巧妙运用了KMP中next数组的精髓，回顾下next数组含义：$next[i]$作为失配指向边，同时也表示字符串前缀$i$的最长公共前后缀的长度。

对于本题，我们先考虑一个字符串的最大周期，自行画画图可以发现最大周期=串长-最短非空公共前后缀长度。

而最长公共前后缀长度即next数组表示的含义，是由前面的next值递推过来的，我们只要不停往前找非$0$的next值，就能得到最短非空公共前后缀的长度，那么根据结论累加答案就好了。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
int n,Next[1000005],j;
char s[1000005];
ll ans;

int main(){
scanf("%d%s",&n,s);
For(i,0,n-1) {
j=i;
while(j){
j=Next[j];
if(s[j]==s[i]){Next[i+1]=j+1;break;}
}
}
For(i,1,n) {
while(Next[Next[i]]) Next[i]=Next[Next[i]];
if(Next[i]) ans+=i-Next[i];
}
cout<<ans;
return 0;
}

0
0 收藏

0 评论
0 收藏
0