题目地址：洛谷：【P3435】[POI2006]OKR-Periods of Words – 洛谷、BZOJ：Problem 1511. — [POI2006]OKR-Periods of Words

题目描述

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.
Task Write a programme that: 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.
一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串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的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.。

输入输出格式

输入格式：
In the first line of the standard input there is one integer k (1≤k≤1 000 000) – the length of the string. In the following line a sequence of exactly k 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.

输入输出样例

输入样例#1：

8
babababa

输出样例#1：

24

题解

想到KMP的fail数组的性质确实挺难，我们来探究下性质。
有字符串abababababab，它的fail数组是0 0 1 2 3 4 5 6 7 8 9 10。我们考虑前缀aba，它最后一个字符的fail是1，说明有一个后缀与到第一个字符为止的前缀相同，把这个相同的部分删去以后的部分ab就是它的一个周期。然后你再尝试一下abab，你会得到相同的结论，而且你会发现i – fail[i]就是这个前缀的最小周期。
有了最小周期，怎么来找最大周期？首先fail为0的前缀是没有周期的，不用说。我们来考虑i和fail[i]周期的关系，删掉fail[i]前缀的多出来那部分（即一个长为fail[i]的后缀）得到的是它的一个周期，而实际上i前缀删掉那一部分也是它的一个周期。这个可以实践一下。
我们又知道，第一个fail不为0的位置求出来的最小周期同时也是它的最大周期，越往后最大周期越大，那么我们就把fail[i]给变成fail[fail[i]]，这样肯定是更优的。最后统计每个位置的i – fail[i]即可。

代码

// Code by KSkun, 2018/3
#include <cstdio>

typedef long long LL;

const int MAXN = 1000005;

int n, fail[MAXN];
char str[MAXN];

inline void calfail() {
    int i = 2, j = 0;
    fail[1] = 0;
    for(; i <= n; i++) {
        while(j && str[j + 1] != str[i]) j = fail[i];
        if(str[j + 1] == str[i]) j++;
        fail[i] = j;
    }
}

int main() {
    scanf("%d%s", &n, str + 1);
    calfail();
    for(int i = 1; i <= n; i++) {
        if(fail[fail[i]]) fail[i] = fail[fail[i]];
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        if(fail[i]) ans += i - fail[i];
    }
    printf("%lld", ans);
    return 0;
}