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)
例题3
这道题找前后缀相等的字符串个数，通过字典树维护前面的字符
class Node:
__slots__ = 'son', 'cnt'
def __init__(self):
self.son = dict()
self.cnt = 0
class Solution:
def calc_z(self, s: str) -> List[int]:
n = len(s)
z = [0] * n
l, r = 0, 0
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
z[0] = n
return z
def countPrefixSuffixPairs(self, words: List[str]) -> int:
n = len(words)
# 前缀与后缀相等 -> Z函数
# Z函数 -> 返回一个数组，数组里是每个子串s[i:]跟原字符串s的最长公共前缀长度
ans = 0
root = Node()
for t in words:
z = self.calc_z(t)
cur = root
# 每个前缀都看看
for i, c in enumerate(t):
if c not in cur.son:
cur.son[c] = Node()
cur = cur.son[c] # 更新字典树
# 通过Z函数判断这个长度的前缀等于后缀
if z[-1 - i] == i + 1:
ans += cur.cnt # 前面符合条件的个数
cur.cnt += 1 # 当前位置+1
return ans
总结
Z函数：对于字符串s，找 s前缀 和 以s[i]开头的后缀 的LCP（最长公共前缀），用到了DP的思想（借用前面的结果）
文章评论