接尾辞の順序とLCPを索引化する

概要

接尾辞順序・LCP索引

全接尾辞の辞書順とLCPを索引化し、部分文字列の順序・出現範囲・順位・distinct数を求める。

考え方

SA・逆順位・LCPの契約

長さNの文字列SについてSA[r]を辞書順r番目の非空接尾辞の開始位置、rank[SA[r]]=rを逆順位とする。LCP[r]はS[SA[r]:]とS[SA[r+1]:]の一致長(r=0,…,N−2)。ライブラリを使う場合も、この配列の添字と空接尾辞を含むかを固定する。

rank[a]<rank[b]なら、二接尾辞の一致長は min LCP[rank[a]:rank[b]] である。共通prefixを持つ接尾辞は辞書順で連続し、両端がh文字一致すればその間も同じprefixを持つ。逆に全隣接対がh文字一致すれば両端も一致するからである。a=bなら一致長はN−a。RMQでこの最小値を取得できる。

出現範囲と長さを切った比較

非空pattern Pをprefixに持つ接尾辞はSA上で連続する。接尾辞の先頭を高々|P|文字だけPと比較し、途中で接尾辞が尽きれば小、P全部が一致すれば同値とする。この比較値が初めて0以上になる位置lo、初めて正になる位置hiを二分探索すると、出現はSA[lo:hi]、個数はhi−lo。一比較O(|P|)なら探索O(|P| log N)、位置列挙は出現数に比例する。通常の文字列比較ではPより長い接尾辞も大となるので、prefix一致用の比較を使う。

一般の部分文字列S[a:a+m]とS[b:b+n]では、接尾辞LCPをhとし q=min(h,m,n) と切る。q<min(m,n)なら次の二文字で大小が決まる。そうでなければ短い方が小さく、長さも等しければ同じ語である。接尾辞rankをそのまま有限長部分文字列の順位にはしない。

distinct数とk番目の復元

SAを順に見ると、位置SA[r]のprefixのうち前の接尾辞との共通長p(r=0なら0、他はLCP[r−1])までは既出で、長さp+1,…,N−SA[r]だけが新しい部分文字列である。以前の接尾辞との最大一致は直前との一致pで得られるため、非空distinct数は Σ_r(N−SA[r]−p)。

これらの新しいprefixを長さ昇順に出すと、全distinct部分文字列の辞書順になる。1-indexのk番目を得るには各rの追加数cnt=N−SA[r]−pを引き、k≤cntとなった接尾辞で長さp+kのprefixを返す。追加数の累積を索引化すればrは二分探索できる。kが総数を超える場合は存在しない。部分文字列の「順位」がdistinct語の順位か、重複する出現の順位かも先に固定する。

巡回shift

S+S上の開始位置a=0,…,N−1から長さNだけ取ると全巡回shiftが得られる。そのSAで開始位置<Nだけを残せば長さNの語の非減少順になるが、長さN以降の違いは同値なshiftのtie breakに過ぎない。隣接する候補のLCPがN以上なら同じshiftとしてまとめる。最小候補から長さNを切り出せば最小巡回shiftを復元できる。

成立条件と計算量

倍増法で各段をrankの整数sortにより線形処理すればO(N log N)、比較sortを各段で使う素朴な実装はO(N log² N)。有界整数文字種のSA-ISはO(N+σ)、LCP構築はO(N)。RMQの構築・query費用を加える。distinct数はO(N²)に達するため整数幅を確保する。空文字列には非空接尾辞・非空distinct語・巡回shiftを作らず、空patternの出現はN+1境界として分ける。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。suffix arrayとLCPの意味を理解し、ライブラリで得た索引を部分文字列queryへ使う。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-suffix-lcp-index

習得する技能

  • 接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。

前提と範囲

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

直接の前提単元: なし。

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

全接尾辞の辞書順と隣接LCPを索引化し、部分文字列の出現範囲・順位・個数へ答える。

このUnitでは扱わないもの

  • rolling hashによる一致比較と回文半径。

根拠