文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズム。
def z_algorithm(S):
l = len(S)
A = [0] * l
i = 1; j = 0
while i < l:
while i + j < l and S[j] == S[i + j]:
j += 1
if not j:
i += 1
continue
A[i] = j
k = 1
while l - i > k < j - A[k]:
A[i + k] = A[k]
k += 1
i += k; j -= k
return A