tbw
↓がわかりやすそう。
トライ木(Trie木) の解説と実装【接頭辞(prefix) を利用したデータ構造】 | アルゴリズムロジック
アルゴリズムの概要
長さ n
の文字列 s
が与えられたとき、以下の条件を満たす (0, 1,..., n - 1 )
の順列 sa
を Suffix Array という。
s[sa[0]..] < s[sa[1]..] < ... < s[sa[n-1]..]
要するに、n個ある suffix のソートができる。
計算量はO(n) (愚直にやるとO(n^2 log n) なので、O(n) で計算できるのはかなりびっくり)
例
abracadabra
による例mississippi
による例Suffix Array でできること
(参考: ACL string )
アルゴリズムの概要
長さ n
の文字列 s
が与えられたとき、以下の条件を満たす長さ n-1
の配列 clp_array
を LCP Array という。
sa
を s
の Suffix Array としたとき clp_array[i]
は s[sa[i]..]
と s[sa[i+1]..]
の LCP の長さ