仮想木の交差・FWTと包除原理・接尾辞配列を活用した高度なアルゴリズム問題の解法
問題1: 仮想木の交差と直径に基づく最適化
問題の分析
木構造上の複数の点集合が与えられ、各グループから1点ずつ選択した際の距離の最大値と最小値の差を求める問題です。各辺の距離が連続しているため、最小値の状態から最大値の状態へ点を移動させる過程を考えると、取り得る距離の値は連続した区間を形成します。したがって、最大値と最小値をそれぞれ独立して求めれば ...
10月14日 12:45 投稿
後綴配列（Suffix Array）の構築と文字列解析への応用
後綴配列（Suffix Array, SA）は、ある文字列のすべての接尾辞（Suffix）を辞書順に並べた配列です。高度な文字列処理において、接尾辞木（Suffix Tree）の代替として、より省メモリで実装しやすいデータ構造として広く利用されます。
基本定義
SA[i]: 全ての接尾辞を辞書順にソートしたとき、第 $i$ 位となる接尾辞の開始位置。
Rank[i]: 位置 $i$ から始まる接 ...
7月7日 02:13 投稿