Z-algorithmで接頭辞との一致を測る

z[i] は文字列の先頭と i 番目からの文字列が何文字一致するかです。すでに一致している区間を再利用します。

言語：Python / 計算量：O(N)

前提：文字列も順番に読める

考え方

1. 右端が最も遠い一致区間 [l,r) を保ちます。
2. i<rなら、既知の一致長を区間内の範囲で流用。
3. その先だけ直接比較し、右端を更新します。

具体例

s="ababa" なら z=[5,0,3,0,1]。添字2からの "aba" は先頭と3文字一致します。

実装

s="ababa";n=len(s);z=[0]*n;l=r=0
for i in range(1,n):
    if i<r:z[i]=min(r-i,z[i-l])
    while i+z[i]<n and s[z[i]]==s[i+z[i]]:z[i]+=1
    if i+z[i]>r:l,r=i,i+z[i]
z[0]=n
print(z)

注意する条件

一致区間の外まで既存値をコピーしてはいけません。z[0]の定義はライブラリごとに確認します。

確認問題

ababa の z[2] は？

実装課題

空でない英小文字文字列 S（長さ≤200000）のZ配列を出す。z[0]=|S|とする。

入力:
ababa
出力:
5 0 3 0 1

s=input().strip();n=len(s);z=[0]*n;l=r=0
for i in range(1,n):
    if i<r:z[i]=min(r-i,z[i-l])
    while i+z[i]<n and s[z[i]]==s[i+z[i]]:z[i]+=1
    if i+z[i]>r:l,r=i,i+z[i]
z[0]=n
print(*z)

読了の記録・下書き・メモへ