算法007-Z算法(kmp算法扩展)

构造字符串的总得分和

你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 si 。

比方说，s = "abaca" ，s1 == "a" ，s2 == "ca" ，s3 == "aca" 依次类推。 si 的 得分 为 si 和 sn 的 最长公共前缀 的长度（注意 s == sn ）。

给你最终的字符串 s ，请你返回每一个 si 的 得分之和 。

1. 示例 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. 示例 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 只包含小写英文字母。

核心思想

用l，r维护一个区间，表示为已匹配的区间，例如：假如已知[l, r]与[0, r - l]区间是一模一样的，此时z[l] = r - l，那么下一个z[l + 1]就可以在[l, r]区间做直接对应的[0, r-l]区间做匹配。
有两种情况，假如z[i]在[l, r]区间内，那么可以直接找对应点z[i - l]看情况，因为在之前已经知道z[l] == z[0]并且一直到z[r] == z[l - r]此时就可以参考z[i-l]，如果他的匹配值都在区间内，那么就可以直接让z[i] = z[i - l]。
假如不在区间内，或者他对应的z[i-l]匹配值超过了r，就去要续在r后继续匹配，直到匹配不成功。

代码

long long sumScores(string s) {
    int n = s.length();
    vector<int> z(n);
    long long ans = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (r >= i && z[i - l] < r - i + 1) { // 在区间，并且可匹配长度也在区间
            z[i] = z[i - l];
        } else { // 不在区间，或者超过r最大值
            z[i] = max(0, r - i + 1);
            while (i + z[i] < n && s[z[i]] == s[z[i] + i]) z[i]++;
        }
        if (i + z[i] - 1 > r) { // 区间有变化就需要重新指定
            l = i;
            r = i + z[i] - 1;
        }
        ans += z[i];
    }

    return ans;
}