接尾辞配列(Suffix-Array)
説明
接尾辞配列。蟻本には $O(N \log^2 N)$ の実装が載っているが, ここでは $O(N \log N)$ の実装を扱う。SA-IS を使えば線形時間で構築できる。
計算量
- Build_SA: $O(N \log N)$
- lower_bound, lower_upper_bound: $O(M\log N)$
- Build_LCA: $O(N)$
実装例
接尾辞配列。蟻本には $O(N \log^2 N)$ の実装が載っているが, ここでは $O(N \log N)$ の実装を扱う。SA-IS を使えば線形時間で構築できる。