https://leetcode.com/problems/sum-of-scores-of-built-strings/
leetcode的hard题目已经开始超纲了，线段树，z函数等等东西层出不穷，真的要好好学习了。
对z函数的考察，记下来备忘。

题目解答

  1. class Solution:
  2.     def sumScores(self, s: str) -> int:
  3.         def zFunc(s):
  4.             z = [0] * len(s)
  5.             l, r = 0, 0
  6.             for i in range(1, len(s)):
  7.                 if i <= r and z[i - l] < r - i + 1:
  8.                         z[i] = z[i - l]
  9.                 else:
  10.                     z[i] = max(0, r - i + 1)
  11.                     while z[i] + i < len(s) and s[z[i]] == s[z[i] + i]:
  12.                         z[i] += 1
  13.                 if i + z[i] - 1 > r:
  14.                     l, r = i, i + z[i] - 1
  15.                 print(i, l, r)
  16.                 print(z)
  17.             return z
  19.         return sum(zFunc(s)) + len(s)

题目分析

首先z函数没什么好说的，记下来就好。
注意，判断是否可以复用前边的结果，是i <= r而不是i < r，等于的情况还是要单独判断的，有可能z[r - l]是0的。

然后说回z函数的算法。其实类似KMP，复用前边的结果，只不过维护最右侧的匹配段，比较难想到，常复习，常思考。
参考：https://oi-wiki.org/string/z-func/
注意仔细过里边的演示，应该比较轻松能明白。

另外，遇到算法题，或者遇到这种不会的算法，不要急着看现成的优雅实现，可以先自己根据思想写个naive版本，程序员的能力，不就是这么训练出来的吗？靠记忆，永远记不完的。