3#ifndef STEP20_SUFFIX_ARRAY_HPP
4#define STEP20_SUFFIX_ARRAY_HPP
21 std::unsigned_integral Size = std::size_t,
22 class Compare = std::less<>>
27 const Char*
data()
const {
return str_.data(); }
28 Size
size()
const {
return str_.size(); }
30 const Compare&
comp()
const {
return comp_; }
34 : str_(std::move(str)), pos_(
size()), comp_(
comp)
36 auto sufs = std::vector<suffix>(
size());
37 auto gen = [i = Size{}]()
mutable {
return suffix{i++, {}}; };
38 auto ch = [&](
auto& suf) {
return str_[suf.pos]; };
39 auto comp_ch = [&](
auto& l,
auto& r) {
return comp_(ch(l), ch(r)); };
40 auto comp_rank = [](
auto& l,
auto& r) {
return l.rank < r.rank; };
41 std::ranges::generate(sufs, gen);
42 fill_first_rank(sufs, comp_ch);
43 for (Size offset = 1; !sorted(sufs); offset *= 2) {
44 fill_second_rank(sufs, offset);
45 fill_first_rank(sufs, comp_rank);
47 std::ranges::transform(sufs, pos_.begin(), &suffix::pos);
50 template <std::ranges::input_range R>
60 std::span<const Size>
find(std::ranges::input_range
auto&& str)
const
62 auto result = std::span{pos_};
63 auto first = std::ranges::begin(str);
64 auto last = std::ranges::end(str);
66 auto ch = [&](Size n) {
return n < str_.size() ? str_[n] : *first; };
67 auto comp = [&](Size l, Size r) {
return comp_(ch(l + i), ch(r + i)); };
68 for (; first != last; ++first, ++i)
69 result = std::ranges::equal_range(result,
size(),
comp);
74 std::basic_string<Char> str_;
75 std::vector<Size> pos_;
80 std::pair<Size, Size> rank;
82 friend void fill_first_rank(std::vector<suffix>& sufs,
auto comp)
84 std::ranges::sort(sufs,
comp);
86 for (Size i = 1; i < sufs.size(); ++i) {
87 bool diff =
comp(sufs[i - 1], sufs[i]);
88 sufs[i - 1].rank.first = acc;
92 sufs.back().rank.first = acc;
95 friend void fill_second_rank(std::vector<suffix>& sufs, Size offset)
97 auto ranks = std::vector<Size>(sufs.size());
98 auto at = [&](Size n) {
return n < ranks.size() ? ranks[n] : 0; };
99 for (
auto& suf : sufs)
100 ranks[suf.pos] = suf.rank.first;
101 for (
auto& suf : sufs)
102 suf.rank.second = at(suf.pos + offset);
105 friend bool sorted(
const std::vector<suffix>& sufs)
107 return sufs.empty() || sufs.back().rank.first == sufs.size();
112template <std::ranges::input_range R,
class Compare = std::less<>>
114 -> suffix_array<std::ranges::range_value_t<R>, std::size_t, Compare>;
120 std::unsigned_integral Size = std::size_t,
121 class Compare = std::less<>>
123 std::vector<Size> lcp_;
126 std::span<const Size>
lcp_array()
const {
return lcp_; }
131 const auto& me = *
this;
132 auto inv = std::vector<Size>(me.size());
133 for (Size i = 0; i < me.size(); ++i)
135 auto first = me.data();
136 auto last = first + me.size();
137 auto eq = equivalence_fn(me.comp());
138 for (Size i = 0, lcp = 0; i < me.size(); ++i, lcp -= !!lcp) {
140 if (Size next = cur + 1; next < me.size()) {
141 auto diff = std::mismatch(
142 first + i + lcp, last, first + me[next] + lcp, last, eq);
143 lcp = diff.first - (first + i);
151 template <std::ranges::input_range R>
159template <std::ranges::input_range R,
class Compare = std::less<>>
161 -> enhanced_suffix_array<std::ranges::range_value_t<R>,
Kasai's algorithm for constructing longest common prefix array.
Definition suffix_array.hpp:122
enhanced_suffix_array(R &&r, const Compare &comp={})
Definition suffix_array.hpp:152
enhanced_suffix_array(suffix_array< Char, Size, Compare > &&arr)
Definition suffix_array.hpp:128
std::span< const Size > lcp_array() const
Definition suffix_array.hpp:126
Manber's algorithm for constructing sorted array of non-empty suffixes.
Definition suffix_array.hpp:23
suffix_array(std::basic_string< Char > str, const Compare &comp={})
Definition suffix_array.hpp:33
Size operator[](Size n) const
suffix position
Definition suffix_array.hpp:29
Size size_type
Definition suffix_array.hpp:26
suffix_array(R &&r, const Compare &comp={})
Definition suffix_array.hpp:51
Char value_type
Definition suffix_array.hpp:25
Size size() const
Definition suffix_array.hpp:28
const Compare & comp() const
Definition suffix_array.hpp:30
const Char * data() const
Definition suffix_array.hpp:27
virtual ~suffix_array()=default
std::span< const Size > find(std::ranges::input_range auto &&str) const
Find positions of suffixes starting with substring.
Definition suffix_array.hpp:60
Definition edit_distance.hpp:11
To to(From &&from)
Definition to.hpp:13