Hard

题目描述

你正在一个字符一个字符地构建长度为 n 的字符串 s，每次将新字符添加到字符串的开头。字符串从 1 到 n 编号，长度为 i 的字符串标记为 si。

例如，对于 s = “abaca”，s1 == “a”，s2 == “ca”，s3 == “aca”，等等。

si 的分数是 si 和 sn 之间最长公共前缀的长度（注意 s == sn）。

给定最终字符串 s，返回每个 si 的分数之和。

示例 1：

输入：s = "babab"
输出：9
解释：
对于 s1 == "b"，最长公共前缀是 "b"，分数为 1。
对于 s2 == "ab"，没有公共前缀，分数为 0。
对于 s3 == "bab"，最长公共前缀是 "bab"，分数为 3。
对于 s4 == "abab"，没有公共前缀，分数为 0。
对于 s5 == "babab"，最长公共前缀是 "babab"，分数为 5。
分数之和为 1 + 0 + 3 + 0 + 5 = 9，所以返回 9。

示例 2：

输入：s = "azbazbzaz"
输出：14
解释：
对于 s2 == "az"，最长公共前缀是 "az"，分数为 2。
对于 s6 == "azbzaz"，最长公共前缀是 "azb"，分数为 3。
对于 s9 == "azbazbzaz"，最长公共前缀是 "azbazbzaz"，分数为 9。
对于所有其他 si，分数为 0。
分数之和为 2 + 3 + 9 = 14，所以返回 14。

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成

解题思路

解题思路

这道题的关键在于理解题意：字符串 si 实际上是原字符串 s 的后缀。我们需要计算每个后缀与整个字符串 s 的最长公共前缀长度，然后求和。

方法一：朴素算法

对每个后缀，直接与原字符串逐字符比较，找出最长公共前缀。时间复杂度为 O(n²)，对于大数据会超时。

方法二：Z算法（推荐）

Z算法是专门解决字符串匹配问题的经典算法。Z[i] 表示从位置 i 开始的子串与整个字符串的最长公共前缀长度。

Z算法的核心思想：

  1. 维护一个窗口 [l, r]，表示当前找到的最右边的匹配区间
  2. 对于每个位置 i，利用已计算的信息来加速计算 Z[i]
  3. 如果 i 在窗口内，可以利用对称性质快速初始化 Z[i]

具体实现：

  • 如果 i <= r，则 Z[i] 初始化为 min(Z[i-l], r-i+1)
  • 然后尝试扩展匹配，更新窗口 [l, r]
  • 累加所有 Z[i] 值即为答案

时间复杂度：O(n)，因为每个字符最多被访问两次 空间复杂度：O(n)，用于存储Z数组

代码实现

class Solution {
public:
    long long sumScores(string s) {
        int n = s.length();
        vector<int> z(n);
        z[0] = n;
        
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = min(z[i - l], r - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        long long result = 0;
        for (int i = 0; i < n; i++) {
            result += z[i];
        }
        return result;
    }
};

class Solution:
    def sumScores(self, s: str) -> int:
        n = len(s)
        z = [0] * n
        z[0] = n
        
        l = r = 0
        for i in range(1, n):
            if i <= r:
                z[i] = min(z[i - l], r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] - 1 > r:
                l = i
                r = i + z[i] - 1
        
        return sum(z)

public class Solution {
    public long SumScores(string s) {
        int n = s.Length;
        int[] z = new int[n];
        z[0] = n;
        
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.Min(z[i - l], r - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += z[i];
        }
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var sumScores = function(s) {
    const n = s.length;
    const z = new Array(n);
    z[0] = n;
    
    let l = 0, r = 0;
    for (let i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = Math.min(z[i - l], r - i + 1);
        } else {
            z[i] = 0;
        }
        while (i + z[i] < n && s[z[i]]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型Z算法朴素算法
时间复杂度O(n)O(n²)
空间复杂度O(n)O(1)

相关题目