原题来自：POI 2006

串是有限个小写字符的序列，特别的，一个空序列也可以是一个串。一个串 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 的最大周期是空串。

给出一个串，求出它所有前缀的最大周期长度之和。

第一行一个整数 k，表示串的长度。

接下来一行表示给出的串。

输出一个整数表示它所有前缀的最大周期长度之和。

8
babababa

24

数据范围:

对于全部数据，1<k<10^6​​ 。

题目分析

这是一道极其经典的字符串进阶题。题目给出了一长串枯燥的定义，核心诉求是：给定一个长度为k的字符串，求出它所有前缀的“最大周期长度”之和。

读懂题意的关键在于理解题目对“周期”的特殊定义：

Q是A的一个proper前缀（真前缀），并且A是QQ的前缀。

这句话在物理空间上意味着什么？ 如果A是QQ的前缀，说明A是由一个完整的Q和一个Q的前缀（或者是完整的Q）拼成的。 我们画图错位比对就会立刻发现：字符串A必然存在一个相等的真前缀和真后缀，且这个相等前后缀的长度正好等于∣A∣−∣Q∣。

题目要求我们寻找最大的周期长度∣Q∣。根据公式∣Q∣=∣A∣−相等前后缀长度，要想让∣Q∣最大，就必须让相等前后缀的长度尽可能小（且非空）。

---

思考过程与解题思路

经过第一步的题意转化，问题已经从“求最大周期”变成了极其明确的KMP靶向问题：求字符串所有前缀的-----最短且非空相等前后缀长度。

我们知道，KMP算法的next数组，求出的是字符串的最长相等真前后缀长度。那“次长”、“第三长”以及“最短”怎么求？ 这里就涉及到了KMP next数组最核心的嵌套传递性质（俄罗斯套娃性质）： 一个前缀的“次长”相等前后缀，其实就是它“最长”相等前后缀的“最长”相等前后缀。

在1-based体系下，这个跳跃序列可以表示为：next[i], next[next[i]], next[next[next[i]]]... 一直跳到0为止，0之前的最后一个非零值，就是我们要找的“最短非空相等前后缀”。

但在现代主流的0-based体系下，这里存在一个极其隐蔽的错位陷阱，也是本题最核心的思维难点。

---

算法设计与优化 (DP 状态压缩)

1. 0-based体系的跳跃错位

在0-based中，nxt[i]存储的是长度，而不是下标。如果 nxt[i]=L，说明最长公共前后缀的长度是L。那么这个长度为L的前缀，它的最后一个字符的真实下标是多少？因为是从0开始计数的，所以它的真实下标是L-1（即 nxt[i]-1）。 因此，在0-base下，正确的次长前后缀查找方式必须是：nxt[nxt[i]-1]。

2. O(1) 的路径压缩 (动态规划思想)

为了找到“最短”，最直接的想法是写一个while循环顺着nxt链一直往回跳。虽然均摊复杂度尚可，但在某些极端构造数据下（如aaaaa...）可能会产生大量重复跳跃。

此时我们观察遍历顺序：我们在main函数中是从左往右（从i=0到k−1）依次计算每个前缀的。 当我们在处理第i个前缀时，它要跳向的下一个位置是nxt[i]-1。显然，这个位置绝对小于i。 这意味着：当我们访问nxt[i]-1时，它的nxt值在之前的循环中，早就已经被我们压缩成“最短”的了。这完全就是动态规划中的记忆化/路径压缩。我们只需要一个简单的if赋值，就能以O(1)的时间直接拿到答案链底端的最短长度。

---

时空复杂度分析

• 时间复杂度： 预处理KMP nxt数组耗时O(N)。

  • 遍历每个前缀并利用路径压缩进行跳跃赋值，每次操作O(1)，总耗时O(N)。

  • 综合时间复杂度为绝对的O(N)。

• 空间复杂度： 需要一个大小为N的nxt数组，空间复杂度为O(N)。

---

同学易错点总结

1. 爆int (WA)： 字符串长度 k≤10^6。所有前缀的最大周期长度之和，极限情况下约为 。必须使用long long存储sum，否则爆 int。

2. 0-based下标越界 (RE)： 必须牢记nxt[i]是长度。去查档案时必须写nxt[nxt[i]-1]。

3. 负数访问 (RE)： 在执行路径压缩前，必须严格判断 if(nxt[i]!=0)。如果某前缀没有公共前后缀（nxt[i]==0），直接减1会导致访问nxt[-1]，直接引发段错误导致程序崩溃。

4. 真实长度映射： 当前循环变量i是0-based下标，代表当前前缀的最后一位。因此当前前缀的真实长度是i+1。

---

完整代码

//这道题深度考察对于kmp的next数组的理解
//由题可知 题目中的proper前缀即为真前缀
//定义Q是A的周期，当且仅当Q是A的一个proper前缀并且A是QQ的前缀
//由这句话可以得到A的前缀（长度为A-Q的部分）和A的后缀是完全匹配的
//A-Q正好是A的一个公共相等前后缀的长度
//需要让Q最大 就是让公共相等前后缀的值尽可能小
//求串A的最大周期长度 等价于先求串A的最短且非空公共相等前后缀长度
//然后用A的长度减去串A的最短且非空公共相等前后缀长度
//即为A的最大周期长度
//根据字符串公共相等前后缀的传递性质 我们可以得到
//字符串的次长公共相等前后缀就是最长公共相等前后缀的公共相等前后缀
//即前缀i的所有公共相等前后缀长度序列为：
//next[i],next[next[i]],next[next[next[i]]],……直到为0
#include <iostream>
using namespace std;

int k;
string s;
long long sum;//存储所有前缀的最大周期长度之和
int len;//存储字符串s的长度
int nxt[1000010];

//求出字符串s的next数组（0-base)
void pre(){
    int j=0;
    //遍历字符串s
    for(int i=1;i<len;i++){
        //如果匹配失败，就让j回到上一个匹配成功的位置
        while(j>0&&s[i]!=s[j]) j=nxt[j-1];
        if(s[i]==s[j]) j++;
        nxt[i]=j;//记录当前以i结尾的子串的最长相等真前后缀长度
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>k>>s;
    len=s.size();//求出字符串s的长度
    //预处理求出s的next数组(0-base)
    pre();
    //需要周期尽可能长 根据|Q|=len-公共相等前后缀 所以需要公共相等前后缀尽可能短
    //接下来求每个前缀的最短公共相等前后缀(0-base)
    //i代表前缀最后一位的真实下标（0-base) 
    //nxt[i]代表的是公共相等前后缀长度（长度不存在0-base概念) 
    //因此需要nxt[i]-1才能得到这个长度在字符串中所对应的真实尾部下标（0-base）
    for(int i=0;i<k;i++){
        //nxt[i]!=0确保当前串有相等前后缀，防nxt[i]-1变-1导致越界
        //nxt[nxt[i]-1]!=0确保还有更短的嵌套前后缀
        if(nxt[i]!=0&&nxt[nxt[i]-1]!=0){
            //DP路径压缩：因为是从前往后遍历，nxt[i]-1之前的记录早就被压缩到了最短
            //所以无需while循环一层层跳，直接 O(1)继承其最短非空记录
            nxt[i]=nxt[nxt[i]-1];
        }
        //如果当前前缀存在非空的相等前后缀
        //因为i对应的是真实下标 所以i+1才对应真实长度
        //最大周期=当前前缀真实长度(i+1)-最短非空相等前后缀长度(nxt[i])
        if(nxt[i]!=0) sum+=(i+1-nxt[i]);
    }
    cout<<sum;
    return 0;
}