题目链接

前缀最大周期长度之和

题目描述

给定一个长度为 的字符串 。对于 的每一个前缀 （其中 从 到 ），都需要计算其“最大周期长度”。最终，输出所有这些长度的总和。

解题思路

本题的核心是正确理解“最大周期”的定义，并利用 KMP 算法中的前缀函数（ 数组）进行高效计算。

关键洞察：周期与 Border

根据题意，“若 是 的真前缀，且 也是 的前缀，则称 为 的周期”。

这一系列的定义可以转化为一个经典的字符串性质：

一个长度为 的字符串 有一个长度为 的周期 （），当且仅当 有一个长度为 的 border（一个既是真前缀又是真后缀的子串）。

题目要求的是“最大周期”，即最长的周期。为了使周期长度 最大，我们需要找到长度 最小的那个非空的 border。

因此，问题被转化为：对于 的每个前缀 （长度为 ），找到其最短非空 border 的长度 ，其最大周期长度就是 。如果不存在非空 border，则最大周期长度为 。

算法步骤

  1. 计算前缀函数( 数组): 首先，我们使用标准 KMP 预处理算法，在 时间内计算出整个字符串 的 数组。 表示前缀 的最长 border 长度。

  2. 计算最短非空 Border: 我们可以通过 数组进行一次动态规划，来找到每个前缀的最短非空 border。

    • 令 表示前缀 （长度为 ）的最短非空 border 长度。
    • 我们知道，一个字符串的所有 border 长度可以通过 值的“失配链”找到，即 。最短的非空 border 就是这个链的末端。
    • 这启发我们建立递推关系：S[0...i-1] 的最短非空 border，要么是其最长 border S[0...k_1-1] 本身，要么是 S[0...k_1-1] 的最短非空 border。
    • 所以，令 。如果 有自己的最短非空 border（即 ），那么 的最短非空 border 和它是一样的，即 。否则，其最短非空 border 就是 本身，即 。

  3. 求和: 有了每个前缀的最短非空 border 长度 之后，我们就可以计算出其最大周期长度。如果 ，则周期长度为 ；否则为 。将所有这些长度累加起来就是最终答案。

代码

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    // 1. 计算 pi 数组
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }

    // 2. 计算 f 数组 (最短非空 border 长度)
    // f[i] 对应前缀 S[0...i-1]
    vector<int> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int k = pi[i - 1];
        if (k > 0) {
            if (f[k] > 0) {
                f[i] = f[k];
            } else {
                f[i] = k;
            }
        }
    }

    // 3. 求和
    long long total_sum = 0;
    for (int i = 1; i <= n; i++) {
        if (f[i] > 0) {
            total_sum += (long long)i - f[i];
        }
    }

    cout << total_sum << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        // 1. 计算 pi 数组
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = pi[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }

        // 2. 计算 f 数组 (最短非空 border 长度)
        // f[i] 对应前缀 S[0...i-1]
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int k = pi[i - 1];
            if (k > 0) {
                if (f[k] > 0) {
                    f[i] = f[k];
                } else {
                    f[i] = k;
                }
            }
        }

        // 3. 求和
        long totalSum = 0;
        for (int i = 1; i <= n; i++) {
            if (f[i] > 0) {
                totalSum += (long)i - f[i];
            }
        }

        System.out.println(totalSum);
    }
}

def solve():
    n = int(input())
    s = input()
    
    # 1. 计算 pi 数组
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
        
    # 2. 计算 f 数组 (最短非空 border 长度)
    # f[i] 对应前缀 S[0...i-1]
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        k = pi[i-1]
        if k > 0:
            if f[k] > 0:
                f[i] = f[k]
            else:
                f[i] = k

    # 3. 求和
    total_sum = 0
    for i in range(1, n + 1):
        if f[i] > 0:
            total_sum += i - f[i]

    print(total_sum)

solve()

算法及复杂度

  • 算法：KMP前缀函数 + 动态规划
  • 时间复杂度：
    • 计算 数组的时间复杂度为 。
    • 计算 数组的时间复杂度为 。
    • 对周期长度求和的时间复杂度为 。
    • 总时间复杂度为线性。
  • 空间复杂度：
    • 用于存储长度为 的 数组和长度为 的 数组。