判断位置： a. 如果 i > R (Case 1)： i. L=i, R=i。 ii. while R < n and S[R] == S[R-L]，R++。 iii. Z[i] = R - L。 iv. R-- (因为 while 循环多加了一次)。 b. 如果 i <= R (Case 2)： i. k = i - L。 ii. 如果 Z[k] < R - i + 1 (Case 2a)，则 Z[i] = Z[k]。 iii. 否则 (Case 2b)，L=i，然后从 R+1 开始朴素比较，更新 R，计算 Z[i]。
返回Z 数组。
Python 实现
def compute_z_array(s: str) -> list[int]:
"""计算字符串 s 的 Z-array"""
n = len(s)
if n == 0:
return []
z = [0] * n
l, r = 0, 0 # Z-box 的左右边界
for i in range(1, n):
# Case 1: i 在 Z-box 外
if i > r:
l, r = i, i
while r < n and s[r] == s[r - l]:
r += 1
z[i] = r - l
r -= 1
# Case 2: i 在 Z-box 内
else:
k = i - l
# Case 2a: Z[k] 不会超出 Z-box
if z[k] < r - i + 1:
z[i] = z[k]
# Case 2b: Z[k] 可能会超出 Z-box
else:
l = i
while r < n and s[r] == s[r - l]:
r += 1
z[i] = r - l
r -= 1
return z
# --- 案例测试 ---
s = "aabcaabxaaaz"
z_values = compute_z_array(s)
print(f"String: {s}")
print(f"Z-array: {z_values}")
# 预期: [0, 1, 0, 0, 3, 1, 0, 0, 3, 1, 1, 0]
复杂度推导过程
时间复杂度: O(n)。
外层 for 循环执行 n-1 次。
内层的 while 循环看起来可能会导致高复杂度，但我们可以通过均摊分析来证明其线性。关键在于 R 指针。R 只会单调向右移动，永不回退。在整个算法中，R 最多从 0 移动到 n-1。while 循环中的字符比较次数，等于 R 指针增加的总次数。因此，所有 while 循环的总执行次数加起来是 O(n) 的。
总时间复杂度为 O(n) + O(n) = O(n)。
空间复杂度: O(n)。
我们需要一个 Z 数组来存储结果，其长度为 n。
应用：使用 Z-Algorithm 进行模式匹配
如何用 Z-Algorithm 实现 KMP 的效果？
构造新字符串：将模式串 P 和文本串 T 用一个不会出现在两者中的特殊字符（如 #）拼接起来，形成新字符串 S = P + "#" + T。
计算 Z-array：计算 S 的 Z-array。
查找匹配：遍历 Z-array。如果 Z[i] 的值等于模式串 P 的长度 m，那么就意味着从 S 的第 i 个位置开始的后缀，其与 S 的前缀（即 P）的匹配长度为 m。这说明我们在 T 中找到了一个 P 的匹配项。其在原始文本串 T 中的起始位置是 i - m - 1。
Python 实现
def z_search(text, pattern):
m = len(pattern)
if m == 0:
return 0
s = pattern + "#" + text
z_array = compute_z_array(s)
for i in range(m + 1, len(s)):
if z_array[i] == m:
return i - m - 1
return -1
# --- 案例测试 ---
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
start_index = z_search(text, pattern)
print(f"在 text 中找到 pattern, 起始索引为: {start_index}") # 预期: 10