suffix_array
// (1)
std::vector<int> suffix_array(const std::vector<int> &s, int upper);
// (2)
template <class T>
std::vector<int> suffix_array(const std::vector<T> &s);
// (3)
std::vector<int> suffix_array(const std::string &s);
概要
Suffix Array
計算量
- 整数・文字列overloadは $O(n+\sigma)$、任意型overloadは $O(n\log n)$
関連項目
lcp_array— suffix arrayの隣接要素間のLCP配列を構築する