【せつびじはいれつ】
接尾辞配列 とは？
公開:
💡 どこから読み始めるかを、辞書順の索引にする
文字列の各位置から末尾までの部分文字列を辞書順に並べ、その開始位置を保存した配列。文字列検索や繰り返しの検出に使える索引。
ひよこ 接尾辞って、言葉の最後に付くもの？
ペンギン先生 ひよこ それをどう並べるの？
ペンギン先生 ひよこ anaを探したいときは？
ペンギン先生 anaで始まる接尾辞が索引のどこに並ぶかを、二分探索で調べられるよ。この例ではanaとananaが該当し、元の位置は3と1。本文での出現順に欲しい場合は、得た位置を並べ直す必要があるね。
ひよこ 二分探索なら検索はO(log n)？
もっと詳しく知りたい人へ
すべての接尾辞をコピーして保存してもよいですか？
長さnの文字列では、コピーする文字数がn＋(n−1)＋…＋1となり、O(n²)の領域を使います。開始位置を保存する表現なら、配列の要素数はnです。隣り合う接尾辞の共通接頭辞長を持つLCP配列などを組み合わせる用途もあります。