Suffix Automatonで部分文字列集合を表す
概要
Suffix Automaton
endpos同値類をstateとし、suffix linkとcloneで全部分文字列の遷移を線形状態数へ圧縮する。
考え方
保持する状態
文字列tの出現が終わる位置集合をendpos(t)とし、同じ集合を持つ部分文字列を一状態へまとめる。状態vの最長文字列の長さをlen[v]、より短い別の同値類へのsuffix linkをlink[v]、文字cを付けた遷移をnext[v][c]とする。vが表す長さはlen[link[v]]+1からlen[v]までで、その範囲の文字列は最長文字列のsuffixである。
初期状態rootはlen=0、link=−1、遷移なし。lastはここまで読んだ文字列全体を表す状態で、最初はrootとする。rootから遷移をたどって読める文字列が全部分文字列であり、suffixだけを受理する用途ではlastからsuffix linkをたどる状態を終状態に指定する。
一文字追加とcloneによる分割
文字cを末尾に追加すると、新しい終了位置を持つのは従来の文字列の各suffixにcを付けた文字列である。そのsuffixをlinkでたどり、次の順で更新する。
- 新状態curを作り、len[cur]=len[last]+1、遷移なしとする。p=lastから始め、p≠−1かつcの遷移がない間、next[p][c]=curを追加してp=link[p]へ進む。
- p=−1ならlink[cur]=rootとする。そうでなければ、最初に見つかった既存遷移の行き先をq=next[p][c]とする。
- len[p]+1=len[q]なら、qの最長文字列も今回のsuffixなのでlink[cur]=qでよい。
- len[p]+1<len[q]なら、qには今回のsuffixより長い文字列も含まれている。短い側だけが新終了位置を得るので、cloneを作り、len[clone]=len[p]+1、next[clone]=next[q]、link[clone]=link[q]とする。遷移表は独立にコピーし、qへの後の変更をcloneに共有しない。
- 分割時はそのpからsuffix linkをたどり、p≠−1かつnext[p][c]=qの間だけ、行き先をcloneへ付け替える。次にlink[q]=link[cur]=cloneとする。cloneのlinkには変更前のlink[q]が入る。最後に、分割の有無によらずlast=curとする。
短い側と長い側は、既存の終了位置から先へ読める文字列が同じなので遷移をコピーできる。一方、新終了位置を得る短いsuffixへ入る遷移だけをcloneへ向け直す。lenとlinkによる長さ区間も、短いcloneと長いqへ分かれ、同値類の不変量を回復する。
例えばabではbとabのendposはいずれも{2}で、同じq(len=2)に属する。bを追加してabbにすると、bのendposは{2,3}、abは{2}となる。lastからb→curを追加した後、rootの既存b遷移はqへ向くが、len[root]+1=1<2。len=1のcloneへrootのb遷移を移し、qとcurのlinkをcloneへ向ける。qはab、cloneはb、curはbbとabbを表す。
成立条件と計算量
一文字につきcur一つと高々一つのcloneを作るので状態数はO(N)。最初の二文字ではcloneが不要なため、N≥2ならrootを含め高々2N−1状態となる。N=0はrootだけ、N=1は2状態である。
構築時間は状態数とは別に、suffix link走査と遷移表の費用を数える。固定サイズの文字種なら新規遷移追加とcloneのコピーは全体O(N)。付け替え走査も全追加を通じた償却O(N)であり、単発の追加はO(N)になり得る。構築算法の償却解析では、付け替えが長いsuffixから短いsuffixへ進み、lastの二つ先のsuffix linkが表す最長suffixの開始位置が前へ戻らないことに課金する。状態数が線形という理由だけで各走査を定数時間とはしない。
固定文字種なら構築O(N)、領域O(N)。文字種数σに対して各状態に配列を確保する実装はO(Nσ)領域・初期化費用となる。平衡木で遷移を保持する実装なら構築O(N log(σ+1))、領域O(N)である。
出現数を求める場合は各curの初期値を1、rootとcloneを0とし、len降順でcnt[link[v]]へcnt[v]を足す。cloneは新しい終了位置を一つ作る状態ではないため1を置かない。lenは0,…,Nなのでbucketで線形時間に並べられる。異なる部分文字列数はroot以外のΣ_v(len[v]−len[link[v]])であり、遷移DAG上の部分文字列DPにも接続できる。
問題一覧
- ABC433 G「Substring Game」 公式問題組合せ: ゲーム状態の勝敗とGrundy数
技能・出典
主題: Suffix Automatonで部分文字列集合を表す(endpos同値類を状態にし、suffix linkと必要なcloneを正しく作って全部分文字列の遷移を線形状態数で表せる。)。既習技能: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。主タグ: Suffix Automaton / 補助タグ: game状態・Grundy DP
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 橙色(2400–2799)。endpos同値類・suffix link・cloneを理解し、全部分文字列を線形状態数で表す。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 文字列アルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-suffix-automaton
習得する技能
- endpos同値類を状態にし、suffix linkと必要なcloneを正しく作って全部分文字列の遷移を線形状態数で表せる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 有限状態automatonの構成。
このUnitを直接前提とする単元: なし。
有限状態で文字列を読む視点を土台に、endpos同値類・suffix link・cloneで全部分文字列を線形状態数に圧縮する。
このUnitでは扱わないもの
- 接尾辞を辞書順に並べるSuffix Array、および複数patternの辞書照合だけを行うAho–Corasick。