class Solution {
public:
long long sumScores(string s) {
}
};
2223. 构造字符串的总得分和
你需要从空字符串开始 构造 一个长度为 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 <= 105s 只包含小写英文字母。原站题解
python3 解法, 执行用时: 736 ms, 内存消耗: 20.1 MB, 提交时间: 2023-10-08 15:18:29
class Solution:
def sumScores(self, s: str) -> int:
n = len(s)
z = [0] * n # z函数
left, right = 0, 0 # 匹配段（Z-box）的闭区间
ans = n # 加上s自身长度n
for i in range(1, n): # 从下标1开始计算z函数
if i <= right and z[i - left] < right - i + 1: # 当前位置处于Z-box中，且处于可确定的匹配范围内（不在Z-box边缘），则无需重复计算而直接得出z[i]
z[i] = z[i - left]
else:
z[i] = max(0, right - i + 1) # （上一个）Z-box的右端可能位于i的左侧
while i + z[i] < n and s[z[i]] == s[i + z[i]]: # 暴力匹配
z[i] += 1 # 公共前缀+1
if i + z[i] - 1 > right: # Z-box区间需更新
left, right = i, i + z[i] - 1
ans += z[i] # z[i]即是s[i:n]与s的最长公众前缀的长度
return ans
golang 解法, 执行用时: 12 ms, 内存消耗: 7.8 MB, 提交时间: 2023-10-08 15:15:42
func sumScores(s string) int64 {
n := len(s)
z := make([]int, n)
ans := n
for i, l, r := 1, 0, 0; i < n; i++ {
z[i] = max(min(z[i-l], r-i+1), 0)
for i+z[i] < n && s[z[i]] == s[i+z[i]] {
l, r = i, i+z[i]
z[i]++
}
ans += z[i]
}
return int64(ans)
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
cpp 解法, 执行用时: 120 ms, 内存消耗: 20.4 MB, 提交时间: 2023-10-08 15:15:14
class Solution {
public:
long long sumScores(string s) {
int n = s.length();
long ans = n;
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
z[i] = max(min(z[i - l], r - i + 1), 0);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
l = i;
r = i + z[i];
++z[i];
}
ans += z[i];
}
return ans;
}
};
java 解法, 执行用时: 18 ms, 内存消耗: 43.1 MB, 提交时间: 2023-10-08 15:14:58
class Solution {
public long sumScores(String s) {
var n = s.length();
var z = new int[n];
long ans = n;
for (int i = 1, l = 0, r = 0; i < n; i++) {
z[i] = Math.max(Math.min(z[i - l], r - i + 1), 0);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
l = i;
r = i + z[i];
z[i]++;
}
ans += z[i];
}
return ans;
}
}
python3 解法, 执行用时: 780 ms, 内存消耗: 19.8 MB, 提交时间: 2023-10-08 15:14:38
'''
Z 函数（扩展KMP）
'''
class Solution:
def sumScores(self, s: str) -> int:
n = len(s)
z = [0] * n
ans, l, r = n, 0, 0
for i in range(1, n):
z[i] = max(min(z[i - l], r - i + 1), 0) # 注：不用 min max，拆开用 < > 比较会更快（仅限于 Python）
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
l, r = i, i + z[i]
z[i] += 1
ans += z[i]
return ans