後綴配列（Suffix Array）の構築と文字列解析への応用
後綴配列（Suffix Array, SA）は、ある文字列のすべての接尾辞（Suffix）を辞書順に並べた配列です。高度な文字列処理において、接尾辞木（Suffix Tree）の代替として、より省メモリで実装しやすいデータ構造として広く利用されます。
基本定義
SA[i]: 全ての接尾辞を辞書順にソートしたとき、第 $i$ 位となる接尾辞の開始位置。
Rank[i]: 位置 $i$ から始まる接 ...
7月7日 02:13 投稿