接頭辞との一致長を再利用する

概要

同じパターンを文字列の各位置と照合するとき、位置を一つずらすたびに先頭から比較し直すと、同じ部分を何度も調べてしまう。既に一致すると分かった区間を先頭側へ対応させ、そこで求めた一致長を再利用するのがZ法の考え方である。

考え方

文字位置は0始まりとする。文字列 SS の位置 ii からの接尾辞 S[i:]S[i:] と、SS 自身の接頭辞が先頭から何文字一致するかを Z[i]Z[i] とする。例えば aaaaa では、位置1から4文字が一致し、位置2からも3文字が一致する。各位置で比較し直すと、位置2以降の aaa が先頭と同じであることを何度も確かめることになる。全て同じ文字なら、長さ NN に対して比較回数は 1+2+⋯+(N−1)1+2+\cdots+(N-1) となり、二次時間かかる。

位置1からの一致を調べた時点で、aaaaa の区間 S[1:5]S[1:5] は先頭の S[0:4]S[0:4] と等しいと分かっている。その中の位置2から始まる部分 S[2:5]S[2:5] は、先頭側の S[1:4]S[1:4] と同じである。従って、位置2からの比較を、既に調べた位置1からの比較へ写せる。この例では末尾までの3文字の一致を再利用できる。

一般には、先頭と等しい既知の区間を半開区間 [l,r)[l,r)、すなわち S[l:r]=S[0:r−l]S[l:r]=S[0:r-l] として保存する。半開区間は左端を含み、右端を含まない。区間内の位置 ii は先頭側の位置 i−li-l に対応するので、そこで求めた Z[i−l]Z[i-l] を使える。ただし、対応が保証されるのは右端 rr の手前までである。区間内で不一致になるならその結果まで再利用でき、一致が右端に達したら、その先を直接調べる。

この「一致区間内の比較を先頭側へ写す」考え方を、下位のZ単元で具体的な文字位置、初期化と更新の手順へ落とし込む。同じパターンとの多数の照合も、パターンを連結文字列の先頭へ置けば、この一致長の計算へ帰着できる。

成立条件と計算量

一文字の比較が O(1)O(1) なら、長さ NN の文字列では O(N)O(N) 時間・空間で全位置の一致長を求められる。再利用で済まない一致比較は既知区間の右端を延ばすので、成功する直接比較の総数は O(N)O(N)。不一致で止まる比較も各位置で高々一回である。パターンと照合先の文字列を連結する場合も、総文字数に対して線形時間で処理できる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。既に調べた一致区間を再利用する考え方へ進む入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 文字列アルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-string-prefix-automata

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 接尾辞・LCPの索引、文字列hash、回文半径。KMPのfailure linkによる逐次照合も本Unitの対象に含めない。

根拠