Zアルゴリズム - taq225's Memo on Algorithms

Zアルゴリズム

Abstract

文字列マッチングの前処理に利用するアルゴリズム.

Explanation

Zアルゴリズム (Z algorithm) は, 長さ$ N の文字列$ Sが与えられたとき,

各接尾辞$ S[i ... N-1] $ (i = 0, \dots, N-1)の接頭辞であり,

$ Sの接頭辞にもなっている

もののうち最長のものの長さを$ Z[i] に格納した配列$ Z[0 ... N-1] を返すアルゴリズム.

すなわち, $ Z[i] = l とすると, $ l \neq 0 のとき$ S[j] = S[i + j]\quad (0 \le j < l) , $ l = 0 のとき$ S[0] \neq S[i] となっている.

Implementation

Input

文字列$ S

Output

上述の配列$ Z[0 ... |S| - 1]

Time complexity

$ O(|S|)time.

code:python

def z_algorithm(S):

N = len(S)

Z = -1 * N; Z0 = N

L = 0; R = 0 # invariant: SL..R is always set to be the longest common prefix of SL..|S| - 1

for i in range(1, N):

if i > R: # naive calculation

j = 0

while i + j < N and Sj == Si + j: j += 1

Zi = j

if j > 0: L = i; R = i + j - 1

else: # i in L, R

k = i - L

if Zk < R - i + 1: Zi = Zk

else:

L = i

while R < N and SR - L == SR: R += 1

Zi = R - L; R -= 1

return Z

Verification

References