質問
文字列 s が与えられたとき、サフィックスオートマトン（SAM）をオンラインで構築してください。extend(c) を実装し、len、link、遷移、および endpos を説明した上で、この構造を利用して異なる部分文字列のカウント、パターンの出現回数のカウント、または最長共通部分文字列の検索を行ってください。状態数が O(n) である理由と、クローンが必要となるタイミングを説明してください。
面接官が見ているポイント
- 単なるトライのノードではなく、状態を
endposの同値類として説明できるかどうか。 - 構築中に直接リンク、ルートリンク、クローン分岐を区別できているかどうか。
len[link[v]] < len[v]、決定性遷移、およびサフィックスリンクトリーの不変条件を維持できるかどうか。- 構造的不変条件をクエリや計算量の結果に結び付けられるかどうか。
模範解答
SAMは、元となる文字列のすべての部分文字列を受理する最小の不完全DFA（partial DFA）です。状態 v は、表現される最大長 len[v] を保持し、link[v] は別の同値類における最長サフィックスを指します。状態は連続する区間 (len[link[v]], len[v]] を表すため、1つの状態で複数の部分文字列の長さを担うことができます。
文字が末尾に追加されたら、cur を作成してサフィックスリンクを辿り、不足している遷移を追加します。既存の遷移先 q が len[p]+1 == len[q] を満たす場合は、cur を直接 q にリンクします。そうでない場合は、q を len = len[p]+1 を持つクローンにコピーし、サフィックスリンクのパス上にある該当の遷移を付け替えて、link[q] と link[cur] の両方がそのクローンを指すようにします。このクローンによって連続長の不変条件が回復されます。
ルート以外のすべての状態は、len[v] - len[link[v]] 個の異なる部分文字列を寄与します。出現回数を数えるには、元の文字列のプレフィックスに対応する状態を1で初期化し、len の降順でサフィックスリンクにカウントを伝播させます。
実装の概要
以下の疑似コードは構築処理を示しています。遷移にはハッシュマップまたは順序付きマップを使用できます。
extend(c):
cur = new state
len[cur] = len[last] + 1
p = last
while p != -1 and c not in next[p]:
next[p][c] = cur
p = link[p]
if p == -1:
link[cur] = root
else:
q = next[p][c]
if len[p] + 1 == len[q]:
link[cur] = q
else:
clone = copy(q)
len[clone] = len[p] + 1
while p != -1 and next[p][c] == q:
next[p][c] = clone
p = link[p]
link[q] = link[cur] = clone
last = curルート以外の状態について len[v] - len[link[v]] の総和を計算すると、異なる部分文字列の数になります。出現回数を求めるには、パターンの状態まで遷移を辿り、長さの降順で伝播されたカウントを読み取ります。
よくある落とし穴
- SAMをすべての
endposクラスの圧縮としてではなく、サフィックスのみを受理するトライとして扱ってしまうこと。 - クローンの遷移をコピーしたものの、そのリンクを不整合なままにしてしまい、その後の長さ区間を壊してしまうこと。
- サフィックスリンクを辿る処理が、
qを指さなくなった最初の状態より前で停止してしまい、リダイレクトする遷移が不足すること。 - すべてのクローンを元文字列のプレフィックスの出現としてカウントしてしまい、全体の出現回数を過大に計上してしまうこと。
- 大きなアルファベットに対してメモリやエンコーディングの前提を明示せずに固定長の遷移配列を使用してしまうこと。
計算量のトレードオフ
固定アルファベットまたはハッシュ化された遷移を使用する場合、構築には O(n) の時間と空間がかかり、状態数は最大で約 2n-1 個になります。順序付きの遷移マップを使用すると、アルファベットの操作に関連するファクターが加わります。SAMは1つの固定テキストに対する多くの部分文字列クエリに非常に適していますが、辞書順走査、LCP処理、キャッシュ局所性に関してはサフィックス配列の方が制御しやすい場合があります。
線形の上限はオンラインでの末尾追加を前提としています。途中への挿入や削除、あるいは両端の更新には異なるデータ構造が必要であり、不変条件を保ったまま extend を単純に再利用することはできません。
空文字列、1文字、同じ文字の繰り返し、および abbb などのクローンを発生させる入力からテストを始めてください。その後、ランダムな文字列を用いて、異なる部分文字列の数や出現回数を力まかせの探索セットと比較します。最長共通部分文字列については、2つ目の文字列をSAMに流し込み、不一致が発生した際にサフィックスリンクを辿ります。
参考資料
- CP-algorithms の SAM ノート：状態区間、クローン構築、およびクエリの計算式。
- Blumer らの最小部分文字列オートマトンに関する論文：理論的な状態数と遷移数の上限。
- カーネギーメロン大学の文字列アルゴリズムノート：サフィックス配列とサフィックスオートマトンの使い分け。
発展的な質問
各状態が連続した長さの区間を表すのはなぜですか？
1つの endpos クラス内の部分文字列は、抜けのない連続した長さのシーケンスを形成します。サフィックスリンクは最長真サフィックスを含む境界クラスを特定するため、その区間は正確に (len[link[v]], len[v]] となります。
クローンが必要になるのはどのような場合ですか？
既存の遷移先 q が len[q] > len[p]+1 を持っている場合、その状態は2つの非連続な長さの範囲を保持しています。その遷移をコピーしてクローンとして分割することで、不変条件が回復されます。
区間の合計が異なる部分文字列の数になるのはなぜですか？
各状態の区間は互いに素であり、表現される各長さは1つの異なる部分文字列に対応します。したがって、各区間のサイズを合計することで、空でないすべての異なる部分文字列が重複なく1回ずつカウントされます。
SAMとAho–Corasick法はどのように比較されるべきですか？
SAMは1つのテキストのすべての部分文字列にインデックスを付け、集約統計をサポートします。Aho–Corasick法は、既知のパターンセットにインデックスを付けて一括マッチングを行います。テキストとパターンセットのどちらが固定されているかによって、通常どちらの構築法が適しているかが決まります。
最長共通部分文字列はどのように見つけますか？
S のSAMを構築し、次に T をスキャンします。現在の一致長を追跡しながら遷移を辿り、不一致が発生した場合はサフィックスリンクを辿って再試行します。観測された最大長を保持します。