[POI2006] OKR-Periods of Words

题面翻译

对于一个仅含小写字母的字符串 \(a\)，\(p\) 为 \(a\) 的前缀且 \(p\ne a\)，那么我们称 \(p\) 为 \(a\) 的 proper 前缀。

规定字符串 \(Q\) 表示 \(a\) 的周期，当且仅当 \(Q\) 是 \(a\) 的 proper 前缀且 \(a\) 是 \(Q+Q\) 的前缀。若这样的字符串不存在，则 \(a\) 的周期为空串。

例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

题目描述

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.

输入格式

In the first line of the standard input there is one integer \(k\) (\(1\le k\le 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

样例输入 #1

8 babababa

样例输出 #1

24

先理解清楚题意：proper前缀可以配合下图理解在这里插入图片描述这里我们不难看出：abcabcab的最长proper字串为abcabc，长度是6。记原来的字符串为\(s\)，proper子串为\(t\)。想想看，如果是要使得proper字串最长，那么恰好就是\(len(s)-min(border)\)。我们可以大致感受一下，如果\(border\)越大，那么对应的\(len(t)\)越小，可以结合上面的例子。那么我们的问题就变成了怎么求最小的\(border\)。问题是，在KMP算法中，\(pmt\)求出来的是\(max(border)\)。我们可以利用KMP算法的一个性质：\(pmt[i]、pmt[pnt[i]]、pmt[pmt[pmt[i]]]······\) 直到为0，以上这些都是\(s\)的\(border\)的长度，并且越来越小。利用这个性质，我们就可以求出来\(min(border)\)。

因为题目是求所有前缀的最大周期长度之和，所以我们令\(j=i+1\)。（因为我个人的KMP写得比较奇怪，题解区的大佬是令\(j=i\)）。然后在\(j>0\)的情况下不断令\(j=pmt[j-1]\)，直到\(j\)最小为止。此时\(ans+=i-j+1\)。这里有一个技巧：当\(j\)求出来后，令\(pmt[i]=j\)，相当于记忆化，否则可能会T。

思路参考：https://www.luogu.com.cn/problem/solution/P3435

贴一下代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
int pmt[MAXN];
ll ans;
inline void get_pmt(const string &s){
    for(int i=1,j=0;i<s.length();i++){
        while(j&&s[i]!=s[j])j=pmt[j-1];
        if(s[i]==s[j])j++;
        pmt[i]=j;
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    get_pmt(s);
    int j=0;
    for(int i=0;i<s.length();i++){
        j=i+1;
        while(pmt[j-1])j=pmt[j-1];
        if(pmt[i])pmt[i]=j;
        ans+=i-j+1;
    }
    cout<<ans;
    return 0;
}