プロンプトと適用場面
接尾辞配列（Suffix Array）は、すべての接尾辞（サフィックス）の開始インデックスを辞書順にソートして格納します。1つの固定テキストに対して多数のパターンクエリが発生する場合、このインデックスを使用することで先頭から再スキャンすることなく一致箇所を見つけることができます。Stanford CS166 では、候補者に searchFor を実装し、すべての一致箇所を返し、出力サイズを考慮することを求めています。ここで m はパターンの長さ、n はテキストの長さ、z は結果の件数です。
面接官が確認しているポイント
- パターンの出現とは、その接尾辞のプレフィックス（接頭辞）がパターンと一致することであると説明できるか。
- 1つの一致で停止するのではなく、lower bound（下限値）を用いて左右の境界を見つけられるか。
- 初回1回限りの構築コストとクエリごとのコストを切り離し、出力に対して O(z) を計上できるか。
- 空のパターン、番兵、重複する接尾辞、および文字比較コストを適切に処理できるか。
最初に確認すべき明確化のための質問
- テキストは固定されており、何度もクエリされますか？テキストが頻繁に変更される場合、接尾辞配列の再構築は適さない可能性があります。
- 出力はすべての開始インデックスを返す必要がありますか、それとも件数のみ、あるいは存在の有無のみですか？
- 大文字小文字の区別、Unicode正規化、バイト単位の順序は定義されていますか？比較関数はその仕様に一致していなければなりません。
- 接尾辞配列は提供されますか、それとも構築する必要がありますか？構築が必要な場合、教育用のソートで十分ですか、それとも線形時間での構築が期待されますか？
30秒での回答
「接尾辞はソートされているため、pattern で始まるすべての接尾辞は1つの連続した区間を形成します。パターンと text[sa[i]:] をプレフィックスで比較し、パターン以上の最初の接尾辞を見つけるために1回の二分探索を、そのプレフィックスを厳密に超える最初の接尾辞を見つけるためにもう1回の二分探索を使用します。区間内のすべての sa の値が一致箇所となるため、出力コストは O(z) であり、クエリは O(m log n + z) になります。慣例として、空のパターンは n+1 個の位置を返します。」
ステップごとの解決策
ステップ 1: 接尾辞配列の意味を定義する
banana の場合、辞書順における接尾辞の開始インデックスは [5, 3, 1, 0, 4, 2] です。この配列は接尾辞文字列のコピーではなく、整数の開始位置を格納します。MITの講義ノートでは、まさにこの辞書順インデックスと二分探索の利用法が説明されています。
ステップ 2: パターンマッチングを区間問題に変換する
ana で始まるすべての接尾辞は隣接しているため、答えは半開区間 [left, right) となります。比較関数には3つの結果が必要です：接尾辞のプレフィックスがパターンより小さい、等しい、または大きい。等しい場合でも、すべての出現箇所を取得するために左右の探索を継続する必要があります。
ステップ 3: 2つの lower bound を実装する
1つ目の lower bound は、パターンより小さくない（パターン以上の）最初の接尾辞プレフィックスを求めます。2つ目は、それを厳密に超える最初の接尾辞プレフィックスを求めるか、一致する範囲の右端を見つけます。パターンと完全な接尾辞を比較するのは誤りです。パターンのプレフィックスであるより短い接尾辞は、パターンより小さいと判定されなければなりません。
ステップ 4: 計算量と構築手法の選択
接尾辞配列が提供されている場合、各比較では最大で m 文字が検査され、二分探索は O(log n) 回の比較を実行するため、クエリは O(m log n + z) となります。Stanford では O(z) の出力コストを明示的に区別しています。教育用の構築では接尾辞のスライスをソートすることもできますが、データをコピーするため低速です。本番環境では、Prefix Doubling、SA-IS、または検証済みのライブラリを使用すべきです。MITおよびStanfordの教材では、接尾辞配列は接尾辞木と比較してポインタによる大量のメモリ消費を抑えられる固定テキスト用インデックスとして位置付けられています。
実行可能なPython実装
def build_suffix_array(text):
# Teaching build for verification, not a production complexity claim.
return sorted(range(len(text)), key=lambda start: text[start:])
def compare_suffix_prefix(text, start, pattern):
suffix = text[start:]
prefix = suffix[:len(pattern)]
if prefix < pattern:
return -1
if prefix > pattern:
return 1
if len(suffix) < len(pattern):
return -1
return 0
def search_with_suffix_array(text, suffix_array, pattern):
if pattern == "":
return list(range(len(text) + 1))
def lower_bound(strict):
lo, hi = 0, len(suffix_array)
while lo < hi:
mid = (lo + hi) // 2
cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
take_right = cmp < 0 or (strict and cmp == 0)
if take_right:
lo = mid + 1
else:
hi = mid
return lo
left = lower_bound(strict=False)
right = lower_bound(strict=True)
return sorted(suffix_array[left:right])このコードは構築とクエリを分離しています。最後のソートは開始インデックスをテキスト順で返します。接尾辞配列の順序がAPIの仕様である場合は省略してください。空のテキスト、空のパターン、一致なし、重複した一致は直接的なテストケースとなります。
質の高い模範解答
「まずテキストが固定されており、多数のパターンを受け取ることを確認し、すべての接尾辞の開始位置を辞書順で格納します。パターンは一致する接尾辞の共通プレフィックスとなるため、すべての解は連続した範囲を占めます。2つの lower bound によってその範囲を特定します。比較ではパターンの長さのみを検査し、より短い接尾辞は小さいものとして扱います。配列が与えられた場合、クエリは O(m log n + z) です（ここで z は出力件数）。教育的な構築にはソートを使用できますが、大規模なインデックスには明確な文字正規化ポリシーとともに、Prefix Doubling、SA-IS、または検証済みの実装が必要です。」
よくある間違い
- 最初の一致のみを返す → 隣接する出現箇所が見逃される → 両方の境界を二分探索する。
- 完全な接尾辞文字列とパターンを比較する → 短い接尾辞の境界が誤る → プレフィックス比較と短い接尾辞のルールを定義する。
- 各クエリに構築コストを計上する → 固定テキストという前提が説明されていない → 1回限りの構築コストとクエリごとのコストを分けて報告する。
- 接尾辞配列の区間順序をテキスト順と呼ぶ → 呼び出し側に不安定な順序が見える → 必要に応じて開始位置をソートするか、順序を文書化する。
- 空のパターンに対する n+1 個の位置を忘れる → 定義された仕様に違反する → 最初に空のパターンを処理する。
フォローアップと優れた回答
長いパターンに対して文字の重複比較を減らすにはどうすればよいですか？
隣接する接尾辞のLCP（最長共通接頭辞）情報を追加し、二分探索中に既知の共通プレフィックスを再利用します。これにより O(m + log n) に近づけることができますが、追加のLCP状態とより厳密な不変条件が必要となります。これらを用いない場合は、誠実に O(m log n) と答えます。
テキストが頻繁に変更される場合でも接尾辞配列を使用しますか？
単一の静的インデックスとしては使用しません。バッチ再構築、セグメント単位のインデックスと後からのマージ、またはオンラインのマッチングアルゴリズムの方が適している場合があります。更新頻度、クエリ量、許容される再構築の遅延に基づいて選択します。
二分探索の境界が正しいことをどのようにテストしますか？
ランダムな小さなテキストとパターンに対する総当たりスキャンと比較します。空のパターン、繰り返される文字、テキストより長いパターン、一致なし、およびすべての位置が一致するケースを含めます。範囲外の隣接する位置がプレフィックスの条件を満たさないことをアサーションで確認します。
直接KMP法を使用しないのはなぜですか？
1つのパターンでテキストを1回だけスキャンする場合、KMPの方が O(n+m) で単純です。接尾辞配列は、固定テキストに対して多数のパターンを処理する場合や、重複部分文字列、LCP、BWTを含むオフライン操作において真価を発揮します。