构造字符串的总得分和

标签: 字符串 二分查找 字符串匹配 后缀数组 哈希函数 滚动哈希

难度: 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 <= 105
  • s 只包含小写英文字母。

Submission

运行时间: 210 ms

内存: 23.8 MB

class Solution:
    def sumScores(self, s: str) -> int:
        def prefix_function(pattern: str):
            m = len(pattern)
            pi = [0] * m
            c = 0
            for i in range(1, m):
                v = pattern[i]
                while c and pattern[c] != v:
                    c = pi[c - 1]
                if pattern[c] == v:
                    c += 1
                pi[i] = c
            return pi

        pi = prefix_function(s)
        n = len(s)
        f = [0] * n
        for i in range(n):
            f[i] = f[pi[i] - 1] + 1
        return sum(f)

Explain

解题思路首先利用了一个字符串处理中的经典算法——KMP算法中的前缀函数（也称为π函数）。前缀函数可以高效地处理字符串的前缀匹配问题。具体到这个题目，我们使用前缀函数来计算字符串s的每个后缀与整个字符串的最长公共前缀。\n\n首先通过前缀函数计算得到数组pi，其中pi[i]表示字符串s[0:i+1]的最长公共前后缀的长度。然后，使用一个额外数组f来记录每个si的得分。对于每个位置i，它的得分f[i]可以通过pi数组递归得到：f[i] = f[pi[i] - 1] + 1。最后，计算f数组中所有数值的总和即可得到答案。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def sumScores(self, s: str) -> int:
        def prefix_function(pattern: str):
            m = len(pattern)
            pi = [0] * m  # 前缀函数数组初始化
            c = 0  # 当前匹配的长度
            for i in range(1, m):
                v = pattern[i]
                while c and pattern[c] != v:
                    c = pi[c - 1]  # 不匹配时回退
                if pattern[c] == v:
                    c += 1  # 匹配则增加匹配长度
                pi[i] = c  # 更新前缀函数数组
            return pi

        pi = prefix_function(s)  # 计算前缀函数
        n = len(s)
        f = [0] * n  # 得分数组初始化
        for i in range(n):
            f[i] = f[pi[i] - 1] + 1  # 递归计算得分
        return sum(f)  # 返回得分之和

Explore

在这个题目中，目标是计算字符串s的每个后缀与整个字符串的最长公共前缀。KMP算法的前缀函数是处理字符串匹配问题的高效工具，它能够快速计算出字符串中每个前缀与后缀的最大公共元素的长度。利用前缀函数能够以线性时间复杂度内完成这个任务，这是因为前缀函数本质上就是为了解决类似问题而设计的。因此，使用KMP的前缀函数可以直接应用于计算字符串的每个后缀和整个字符串的匹配长度，从而高效地解决问题。

在计算前缀函数时，当当前字符不匹配时使用`c = pi[c - 1]`进行回退，是为了找到一个较短的已知前缀，该前缀仍然是当前考虑的后缀的一部分。这种逻辑的正确性在于：如果长前缀失败了，则可以尝试在此前缀的基础上最长的合法前缀，因为这仍然可能是一个有效的匹配开始。这种方式确保了算法不会漏掉可能的匹配前缀，同时避免重复检查已经失败的匹配，从而保持算法的高效性。

递归计算得分`f[i] = f[pi[i] - 1] + 1`的意义在于，`f[i]`表示以索引`i`结尾的子字符串的得分，而`pi[i] - 1`是这个子字符串最长公共前后缀的前一个字符的索引。因此，`f[pi[i] - 1]`表示最长公共前后缀的得分。`+1`代表当前子字符串相较于其前缀函数指示的前一子字符串，额外增加的一个匹配单元，即当前字符本身也构成了一个有效匹配的单元。

在计算得分数组`f`时，可以保证`pi[i] - 1`总是一个有效的索引，这是因为`pi[i]`的值始终大于等于0（即至少是0）。当`pi[i]`为0时，`pi[i] - 1`结果为-1，通常用于表示不存在前缀的情况。在实际计算`f[i]`时，需要检查`pi[i]`是否为0来避免负索引访问数组`f`。如果`pi[i]`是0，则`f[i] = 1`，表示只有当前字符自身形成长度为1的新得分。因此，算法中需要适当处理这种边界情况，以确保不会出现数组越界错误。