Z函数的原理和应用：以Python为例

Z函数

也就是，它想找前缀和以s[i]开头的后缀的LCP

思想

维护一个右端点最右的z-box
结合z[i - l]的结果和朴素算法进行优化

Z函数Python模版

def sumScores(self, s: str) -> int:
    n = len(s)
    z = [0] * n
    l = r = 0 # 右端点最右的z-box
    for i in range(1, n):
        if i <= r: # 沿用之前的结果
            z[i] = min(z[i - l], r - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]: # 朴素写法
            l, r = i, i + z[i]
            z[i] += 1
    return z

例题1

这道题希望找到z函数中满足i为k的倍数，且z[i]可以完全匹配完从i开始的后缀的最小值

class Solution:
    def minimumTimeToInitialState(self, s: str, k: int) -> int:
        n = len(s)
        z = [0] * n
        l = r = 0 # 右端点最右的z-box
        for i in range(1, n):
            if i <= r: # 沿用之前的结果
                z[i] = min(z[i - l], r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]: # 朴素写法
                l, r = i, i + z[i]
                z[i] += 1
            if i % k == 0 and z[i] == n - i: # 前缀和后缀完全匹配
                return i // k
        return int(ceil(n / k))

例题2

这道题求z函数之和，由于z函数不包括原字符串，所以要加上原字符串长度

class Solution:
    def sumScores(self, s: str) -> int:
        n = len(s)
        z = [0] * n
        l = r = 0 # 右端点最右的z-box
        for i in range(1, n):
            if i <= r: # 沿用之前的结果
                z[i] = min(z[i - l], r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]: # 朴素写法
                l, r = i, i + z[i]
                z[i] += 1
        return sum(z) + len(s)

总结

Z函数：对于字符串s，找 s前缀 和 以s[i]开头的后缀 的LCP（最长公共前缀），用到了DP的思想（借用前面的结果）

参考文献

oi-wiki
z函数知乎高赞回答