アルゴリズム・データ構造図鑑 · 基礎から応用へ

Zアルゴリズム:先頭との一致長をまとめて求める

既知の一致区間を再利用してZ配列を線形時間で作り、区切り文字を使ったパターン検索へつなぐ。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 各位置から先頭と何文字一致するか
  2. 既知の区間を再利用する
  3. パターンと本文を連結する
  4. 線形時間の意味と範囲
  5. この記事をロゲイアに質問する理解を確かめる

各位置から先頭と何文字一致するか

文字列sのZ[i]は、位置iから始まる部分とsの先頭が何文字続けて一致するかを表します。ここではZ[0]=0という約束を使い、0以外の位置について値を求めます。例えばababaなら[0,0,3,0,1]です。位置2からはabaが先頭と一致し、位置4からはaだけが一致します。接頭辞関数のように各接頭辞の最長の境界を直接記録する配列ではなく、各開始位置の一致長を記録しています。二つの配列の定義や添字を混ぜないことが実装の第一歩です。

既知の区間を再利用する

右端が最も先まで分かっている一致区間[L,R)を持ちます。この区間の部分文字列はsの先頭の長さR−Lと等しいので、iが区間内ならZ[i−L]を参考にできます。ただし既知の区間の外へそのままコピーせず、まずmin(Z[i−L],R−i)を使います。その長さが右端に届く場合は、R以降の文字を実際に比較して延長します。単に以前の値を丸ごと写すと、まだ確認していない部分まで一致していると誤認するため、既知の範囲による上限が必要です。

パターンと本文を連結する

パターンP、どちらにも含まれない区切り記号、テキストTを連結したP#Tを考えます。P=aba、T=ababaなら、連結列の位置4と6でZの値が3以上になり、Tの位置0と2の一致が分かります。連結列の位置からm+1を引いて本文の位置へ戻します。区切り記号が入力に混じる可能性があるなら、文字一つを適当に選ぶのでなく、入力アルファベット外の番兵を表せる型を使うなどの対処が必要です。重なる出現も値を調べるだけで拾えます。

線形時間の意味と範囲

一致区間の右端Rは後ろへ戻らず、新しい文字を確認して延長できる回数は文字列長に比例します。各位置の初期処理を合わせても、長さNのZ配列はO(N)時間、O(N)領域です。Z配列全体を返すインターフェースなら、この領域は出力のためにも必要です。文字比較が定数時間であることを前提とし、バイト・コードポイント・正規化後の要素など、どの単位を比較しているかを明記します。空入力や同一文字の長い列は境界を確認する良いテストになります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ