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

题目求的就是扩展 KMP（Z 数组）的所有元素之和。

指路 -> https://oi-wiki.org/string/z-func/

[sol1-Python3]

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

[sol1-Java]

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;
    }
}

[sol1-C++]

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;
    }
};

[sol1-Go]

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 }