GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 88.3% 573 / 0 / 649
Functions: 81.2% 26 / 0 / 32
Branches: 95.1% 365 / 18 / 402
suffix_array.hpp
Line Branch Exec Source
1 #pragma once
2
3 /*
4 * This is mostly inspired by https://golang.org/src/index/suffixarray/sais.go.
5 */
6
7 #include <algorithm>
8 #include <vector>
9 #include <string>
10 #include <cassert>
11 #include <cstring>
12 #include <type_traits>
13
14 #include "rmq.hpp"
15
16
2/4
int sz<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 22135549 times.
int sz<std::vector<char, std::allocator<char> > const&>(std::vector<char, std::allocator<char> > const&):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 98 times.
 22135647 template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
17
18 // Layered suffix array: SuffixArrayBase computes just sa/rank, each further
19 // layer statically opts into one more derived structure. Use the leaf classes
20 // SuffixArray, SuffixArrayLCP, or SuffixArrayRMQ; the named constructors on
21 // each return that type.
22 50 template <typename Self> class SuffixArrayBase {
23 public:
24 using index_t = int;
25 int N;
26 std::vector<index_t> sa;
27 std::vector<index_t> rank;
28
29 74 SuffixArrayBase() : N(0) {}
30
31 74 template <typename String> static Self construct_raw(const String& S, index_t sigma) {
32 74 Self res;
33
2/2
SuffixArray SuffixArrayBase<SuffixArray>::construct_raw<std::vector<char, std::allocator<char> > >(std::vector<char, std::allocator<char> > const&, int):
✓ Branch 2 → 3 taken 50 times.
SuffixArrayLCP SuffixArrayBase<SuffixArrayLCP>::construct_raw<std::vector<char, std::allocator<char> > >(std::vector<char, std::allocator<char> > const&, int):
✓ Branch 2 → 3 taken 24 times.
 74 res.build(S, sigma);
34 74 return res;
35 }
36
37 // Pass a function which returns a value in [0, sigma)
38 ✗ template <typename String, typename F> static Self map_and_construct(const String& S, const F& f, int sigma) {
39 ✗ std::vector<decltype((f(S[0])))> mapped(sz(S));
40 ✗ for (int i = 0; i < sz(S); i++) {
41 ✗ mapped[i] = f(S[i]);
42 ✗ assert(0 <= int(mapped[i]) && int(mapped[i]) < sigma);
43 }
44 ✗ return construct_raw(mapped, sigma);
45 }
46
47 // Sorts the elements of S and then runs suffix array. This takes O(N log N) time with no dependence on sigma.
48 ✗ template <typename String> static Self sort_and_construct(const String& S) {
49 using std::begin;
50 using std::end;
51 ✗ using value_type = typename std::iterator_traits<decltype(begin(S))>::value_type;
52 using compressed_value_type = typename std::conditional<
53 sizeof(value_type) < sizeof(index_t),
54 value_type,
55 index_t
56 >::type;
57
58 ✗ std::vector<compressed_value_type> compressed_s(sz(S));
59 ✗ int sigma = 0;
60
61 {
62 ✗ std::vector<value_type> vals(begin(S), end(S));
63 ✗ std::sort(vals.begin(), vals.end());
64 ✗ vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
65 ✗ for (int i = 0; i < sz(S); i++) {
66 ✗ compressed_s[i] = compressed_value_type(index_t(std::lower_bound(vals.begin(), vals.end(), S[i]) - vals.begin()));
67 }
68 ✗ sigma = int(vals.size());
69 }
70
71 ✗ return construct_raw(compressed_s, sigma);
72 }
73
74 // Shifts the elements so that sigma = max(S) - min(S) + 1
75 74 template <typename String> static Self shift_and_construct(const String& S) {
76 using std::begin;
77 using std::end;
78 using value_type = typename std::iterator_traits<decltype(begin(S))>::value_type;
79
80 74 std::vector<value_type> compressed_s(sz(S));
81 74 int sigma = 0;
82
83
2/4
SuffixArray SuffixArrayBase<SuffixArray>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✓ Branch 3 → 4 taken 50 times.
✗ Branch 3 → 12 not taken.
SuffixArrayLCP SuffixArrayBase<SuffixArrayLCP>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✓ Branch 3 → 4 taken 24 times.
✗ Branch 3 → 12 not taken.
 74 if (sz(S) > 0) {
84 74 value_type lo = *begin(S), hi = *begin(S);
85
6/8
SuffixArray SuffixArrayBase<SuffixArray>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 50 times.
✓ Branch 8 → 7 taken 13584543 times.
✓ Branch 8 → 10 taken 50 times.
SuffixArrayLCP SuffixArrayBase<SuffixArrayLCP>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 24 times.
✓ Branch 8 → 7 taken 8550784 times.
✓ Branch 8 → 10 taken 24 times.
 22135401 for (const auto& x : S) {
86 22135327 if (x < lo) lo = x;
87 22135327 if (x > hi) hi = x;
88 }
89
90
4/4
SuffixArray SuffixArrayBase<SuffixArray>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✓ Branch 10 → 9 taken 13584543 times.
✓ Branch 10 → 11 taken 50 times.
SuffixArrayLCP SuffixArrayBase<SuffixArrayLCP>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✓ Branch 10 → 9 taken 8550784 times.
✓ Branch 10 → 11 taken 24 times.
 22135401 for (int i = 0; i < sz(S); i++) {
91 22135327 compressed_s[i] = value_type(S[i] - lo);
92 }
93 74 sigma = int(hi - lo + 1);
94 }
95
96
2/2
SuffixArray SuffixArrayBase<SuffixArray>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✓ Branch 12 → 13 taken 50 times.
SuffixArrayLCP SuffixArrayBase<SuffixArrayLCP>::shift_and_construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&):
✓ Branch 12 → 13 taken 24 times.
 74 return construct_raw(compressed_s, sigma);
97 74 }
98
99 // Renumber/filter to only the used elements with bucket sorting. Still takes O(max(S) - min(S) + 1) memory/time,
100 // but should be less memory than `shift_and_construct` when sigma ~ N and max(S) - min(S) + 1 > N.
101 ✗ template <typename String> static Self bucket_and_construct(const String& S) {
102 using std::begin;
103 using std::end;
104 ✗ using value_type = typename std::iterator_traits<decltype(begin(S))>::value_type;
105 using compressed_value_type = typename std::conditional<
106 sizeof(value_type) < sizeof(index_t),
107 value_type,
108 index_t
109 >::type;
110
111 ✗ std::vector<compressed_value_type> compressed_s(sz(S));
112 ✗ int sigma = 0;
113
114 ✗ if (sz(S) > 0) {
115 ✗ value_type lo = *begin(S), hi = *begin(S);
116 ✗ for (const auto& x : S) {
117 ✗ if (x < lo) lo = x;
118 ✗ if (x > hi) hi = x;
119 }
120
121 ✗ std::vector<compressed_value_type> buckets(hi - lo + 1, 0);
122 ✗ for (const auto& x : S) {
123 ✗ buckets[x - lo] = 1;
124 }
125 ✗ for (int v = 0; v < int(buckets.size()); v++) {
126 ✗ if (buckets[v]) buckets[v] = compressed_value_type(sigma++);
127 }
128
129 ✗ for (int i = 0; i < sz(S); i++) {
130 ✗ compressed_s[i] = buckets[S[i] - lo];
131 }
132 }
133
134 ✗ return construct_raw(compressed_s, sigma);
135 }
136
137 protected:
138 74 template <typename String> void build(const String& S, index_t sigma) {
139 74 N = sz(S);
140 74 build_sa(S, sigma);
141 74 build_rank();
142 74 }
143
144 private:
145 74 template <typename String> void build_sa(const String& S, index_t sigma) {
146
2/4
void SuffixArrayBase<SuffixArray>::build_sa<std::vector<char, std::allocator<char> > >(std::vector<char, std::allocator<char> > const&, int):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 50 times.
void SuffixArrayBase<SuffixArrayLCP>::build_sa<std::vector<char, std::allocator<char> > >(std::vector<char, std::allocator<char> > const&, int):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 24 times.
 74 sa = std::vector<index_t>(N+1);
147 74 assert(sigma >= 0);
148 22135401 for (auto s : S) assert(0 <= index_t(s) && index_t(s) < sigma);
149 74 std::vector<index_t> tmp(sigma + std::max(N, sigma));
150 74 SuffixArrayBase::sais<String>(N, S, sa.data(), sigma, tmp.data());
151 74 }
152
153 266 template <typename String> static void sais(int N, const String& S, index_t* sa, int sigma, index_t* tmp) {
154
4/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 115 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 50 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 77 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 24 times.
 266 if (N == 0) {
155 ✗ sa[0] = 0;
156 1 return;
157
5/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 115 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 4 → 5 taken 1 time.
✓ Branch 4 → 6 taken 49 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 77 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 24 times.
 266 } else if (N == 1) {
158 1 sa[0] = 1;
159 1 sa[1] = 0;
160 1 return;
161 }
162
163 // Phase 1: Initialize the frequency array, which will let us lookup buckets.
164 265 index_t* freq = tmp; tmp += sigma;
165 265 memset(freq, 0, sizeof(*freq) * sigma);
166
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 8 → 7 taken 4155125 times.
✓ Branch 8 → 9 taken 115 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 8 → 7 taken 13584542 times.
✓ Branch 8 → 9 taken 49 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 8 → 7 taken 2942897 times.
✓ Branch 8 → 9 taken 77 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 8 → 7 taken 8550784 times.
✓ Branch 8 → 9 taken 24 times.
 29233613 for (int i = 0; i < N; i++) {
167 29233348 ++freq[index_t(S[i])];
168 }
169 1273 auto build_bucket_start = [&]() {
170 504 int cur = 1;
171
2/2
✓ Branch 4 → 3 taken 4216098 times.
✓ Branch 4 → 5 taken 504 times.
 4216602 for (int v = 0; v < sigma; v++) {
172 4216098 tmp[v] = cur;
173 4216098 cur += freq[v];
174 }
175 };
176 2281 auto build_bucket_end = [&]() {
177 1008 int cur = 1;
178
2/2
✓ Branch 4 → 3 taken 8432196 times.
✓ Branch 4 → 5 taken 1008 times.
 8433204 for (int v = 0; v < sigma; v++) {
179 8432196 cur += freq[v];
180 8432196 tmp[v] = cur;
181 }
182 };
183
184 265 int num_pieces = 0;
185
186 265 int first_endpoint = 0;
187 // Phase 2: find the right-endpoints of the pieces
188 {
189 265 build_bucket_end();
190
191 // Initialize the final endpoint out-of-band this way so that we don't try to look up tmp[-1].
192 // This doesn't count towards num_pieces.
193 265 sa[0] = N;
194
195 265 index_t c0 = S[N-1], c1 = -1; bool isS = false;
196
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 15 → 11 taken 4155010 times.
✓ Branch 15 → 16 taken 115 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 15 → 11 taken 13584493 times.
✓ Branch 15 → 16 taken 49 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 15 → 11 taken 2942820 times.
✓ Branch 15 → 16 taken 77 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 15 → 11 taken 8550760 times.
✓ Branch 15 → 16 taken 24 times.
 29233348 for (int i = N-2; i >= 0; i--) {
197 29233083 c1 = c0;
198
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 11 → 12 taken 9974128 times.
✓ Branch 11 → 14 taken 3610365 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 11 → 12 taken 5684871 times.
✓ Branch 11 → 14 taken 2865889 times.
 29233083 c0 = S[i];
199
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 11 → 12 taken 2149980 times.
✓ Branch 11 → 14 taken 2005030 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 11 → 12 taken 9974128 times.
✓ Branch 11 → 14 taken 3610365 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 11 → 12 taken 1544213 times.
✓ Branch 11 → 14 taken 1398607 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 11 → 12 taken 5684871 times.
✓ Branch 11 → 14 taken 2865889 times.
 29233083 if (c0 < c1) {
200 isS = true;
201
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 12 → 13 taken 1631916 times.
✓ Branch 12 → 14 taken 518064 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 12 → 13 taken 2689666 times.
✓ Branch 12 → 14 taken 7284462 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 12 → 13 taken 1064839 times.
✓ Branch 12 → 14 taken 479374 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 12 → 13 taken 2025781 times.
✓ Branch 12 → 14 taken 3659090 times.
 19353192 } else if (c0 > c1 && isS) {
202 7412202 isS = false;
203 // insert i+1
204 7412202 sa[first_endpoint = --tmp[c1]] = i+1;
205 7412202 ++num_pieces;
206 }
207 }
208 }
209
210 // If num_pieces <= 1, we don't need to actually run the recursion, it's just sorted automatically
211 // Otherwise, we're going to rebucket
212
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 16 → 17 taken 111 times.
✓ Branch 16 → 76 taken 4 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 16 → 17 taken 38 times.
✓ Branch 16 → 76 taken 11 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 16 → 17 taken 73 times.
✓ Branch 16 → 76 taken 4 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 16 → 17 taken 17 times.
✓ Branch 16 → 76 taken 7 times.
 265 if (num_pieces > 1) {
213 // Remove the first endpoint, we don't need to run the IS on this
214 239 sa[first_endpoint] = 0;
215
216 // Run IS for L-type
217 {
218 239 build_bucket_start();
219
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 27 → 19 taken 4155221 times.
✓ Branch 27 → 28 taken 111 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 27 → 19 taken 9596426 times.
✓ Branch 27 → 28 taken 38 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 27 → 19 taken 2942955 times.
✓ Branch 27 → 28 taken 73 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 27 → 19 taken 6086915 times.
✓ Branch 27 → 28 taken 17 times.
 22781756 for (int z = 0; z <= N; z++) {
220 22781517 int v = sa[z];
221
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 19 → 20 taken 419770 times.
✓ Branch 19 → 21 taken 3735451 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 19 → 20 taken 1494270 times.
✓ Branch 19 → 21 taken 8102156 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 19 → 20 taken 380328 times.
✓ Branch 19 → 21 taken 2562627 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 19 → 20 taken 1086082 times.
✓ Branch 19 → 21 taken 5000833 times.
 22781517 if (!v) continue;
222
223 // Leave for the S-round
224
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 21 → 22 taken 1631913 times.
✓ Branch 21 → 23 taken 2103538 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 21 → 22 taken 2689663 times.
✓ Branch 21 → 23 taken 5412493 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 21 → 22 taken 1064836 times.
✓ Branch 21 → 23 taken 1497791 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 21 → 22 taken 2025780 times.
✓ Branch 21 → 23 taken 2975053 times.
 19401067 if (v < 0) continue;
225
226 // clear out our garbage
227 11988875 sa[z] = 0;
228
229 11988875 --v;
230
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 23 → 24 taken 2689663 times.
✓ Branch 23 → 25 taken 2722830 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 23 → 24 taken 2025780 times.
✓ Branch 23 → 25 taken 949273 times.
 11988875 index_t c0 = S[v-1], c1 = S[v];
231
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 23 → 24 taken 1631913 times.
✓ Branch 23 → 25 taken 471625 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 23 → 24 taken 2689663 times.
✓ Branch 23 → 25 taken 2722830 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 23 → 24 taken 1064836 times.
✓ Branch 23 → 25 taken 432955 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 23 → 24 taken 2025780 times.
✓ Branch 23 → 25 taken 949273 times.
 19401067 sa[tmp[c1]++] = (c0 < c1) ? ~v : v;
232 }
233 }
234
235 239 index_t* const sa_end = sa + N + 1;
236
237 239 index_t* pieces = sa_end;
238 // Run IS for S-type and compactify
239 {
240 239 build_bucket_end();
241
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 38 → 30 taken 4155221 times.
✓ Branch 38 → 39 taken 111 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 38 → 30 taken 9596426 times.
✓ Branch 38 → 39 taken 38 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 38 → 30 taken 2942955 times.
✓ Branch 38 → 39 taken 73 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 38 → 30 taken 6086915 times.
✓ Branch 38 → 39 taken 17 times.
 22781756 for (int z = N; z >= 0; z--) {
242 22781517 int v = sa[z];
243
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 30 → 31 taken 471918 times.
✓ Branch 30 → 32 taken 3683303 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 30 → 31 taken 2878302 times.
✓ Branch 30 → 32 taken 6718124 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 30 → 31 taken 433145 times.
✓ Branch 30 → 32 taken 2509810 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 30 → 31 taken 949323 times.
✓ Branch 30 → 32 taken 5137592 times.
 22781517 if (!v) continue;
244
245 // clear our garbage
246 18048829 sa[z] = 0;
247
248
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 32 → 33 taken 1631913 times.
✓ Branch 32 → 34 taken 2051390 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 32 → 33 taken 2689663 times.
✓ Branch 32 → 34 taken 4028461 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 32 → 33 taken 1064836 times.
✓ Branch 32 → 34 taken 1444974 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 32 → 33 taken 2025780 times.
✓ Branch 32 → 34 taken 3111812 times.
 18048829 if (v > 0) {
249 7412192 *--pieces = v;
250 7412192 continue;
251 }
252
253 10636637 v = ~v;
254
255 10636637 --v;
256
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 34 → 35 taken 1338798 times.
✓ Branch 34 → 36 taken 2689663 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 34 → 35 taken 1086032 times.
✓ Branch 34 → 36 taken 2025780 times.
 10636637 index_t c0 = S[v-1], c1 = S[v];
257
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 34 → 35 taken 419477 times.
✓ Branch 34 → 36 taken 1631913 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 34 → 35 taken 1338798 times.
✓ Branch 34 → 36 taken 2689663 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 34 → 35 taken 380138 times.
✓ Branch 34 → 36 taken 1064836 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 34 → 35 taken 1086032 times.
✓ Branch 34 → 36 taken 2025780 times.
 10636637 sa[--tmp[c1]] = (c0 > c1) ? v : ~v;
258 }
259 }
260
261 // Compute the lengths of the pieces in preparation for equality
262 // comparison, and store them in sa[v/2]. We set the length of the
263 // final piece to 0; it compares unequal to everything because of
264 // the sentinel.
265 {
266 239 int prv_start = N;
267 239 index_t c0 = S[N-1], c1 = -1; bool isS = false;
268
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 46 → 40 taken 4154999 times.
✓ Branch 46 → 53 taken 111 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 46 → 40 taken 9596350 times.
✓ Branch 46 → 53 taken 38 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 46 → 40 taken 2942809 times.
✓ Branch 46 → 53 taken 73 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 46 → 40 taken 6086881 times.
✓ Branch 46 → 53 taken 17 times.
 22781278 for (int i = N-2; i >= 0; i--) {
269 22781039 c1 = c0;
270
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 40 → 41 taken 5985991 times.
✓ Branch 40 → 45 taken 3610359 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 40 → 41 taken 3220995 times.
✓ Branch 40 → 45 taken 2865886 times.
 22781039 c0 = S[i];
271
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 40 → 41 taken 2149972 times.
✓ Branch 40 → 45 taken 2005027 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 40 → 41 taken 5985991 times.
✓ Branch 40 → 45 taken 3610359 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 40 → 41 taken 1544205 times.
✓ Branch 40 → 45 taken 1398604 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 40 → 41 taken 3220995 times.
✓ Branch 40 → 45 taken 2865886 times.
 22781039 if (c0 < c1) {
272 isS = true;
273
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 41 → 42 taken 1631913 times.
✓ Branch 41 → 45 taken 518059 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 41 → 42 taken 2689663 times.
✓ Branch 41 → 45 taken 3296328 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 41 → 42 taken 1064836 times.
✓ Branch 41 → 45 taken 479369 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 41 → 42 taken 2025780 times.
✓ Branch 41 → 45 taken 1195215 times.
 12901163 } else if (c0 > c1 && isS) {
274 7412192 isS = false;
275
276 // insert i+1
277 7412192 int v = i+1;
278
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 42 → 43 taken 1631802 times.
✓ Branch 42 → 44 taken 111 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 42 → 43 taken 2689625 times.
✓ Branch 42 → 44 taken 38 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 42 → 43 taken 1064763 times.
✓ Branch 42 → 44 taken 73 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 42 → 43 taken 2025763 times.
✓ Branch 42 → 44 taken 17 times.
 7412192 sa[v>>1] = prv_start == N ? 0 : prv_start - v;
279 7412192 prv_start = v;
280 }
281 }
282 }
283
284 // Compute the alphabet, storing the result into sa[v/2].
285 int next_sigma = 0;
286 {
287 int prv_len = -1, prv_v = 0;
288
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 53 → 47 taken 1631913 times.
✓ Branch 53 → 54 taken 111 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 53 → 47 taken 2689663 times.
✓ Branch 53 → 54 taken 38 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 53 → 47 taken 1064836 times.
✓ Branch 53 → 54 taken 73 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 53 → 47 taken 2025780 times.
✓ Branch 53 → 54 taken 17 times.
 7412431 for (int i = 0; i < num_pieces; i++) {
289 7412192 int v = pieces[i];
290 7412192 int len = sa[v>>1];
291
292 7412192 bool eq = prv_len == len;
293
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 49 → 48 taken 2434016 times.
✓ Branch 49 → 50 taken 1631913 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 49 → 48 taken 5486724 times.
✓ Branch 49 → 50 taken 2689663 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 49 → 48 taken 1419229 times.
✓ Branch 49 → 50 taken 1064836 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 49 → 48 taken 4234254 times.
✓ Branch 49 → 50 taken 2025780 times.
 20986415 for (int a = 0; eq && a < len; ++a) {
294 13574223 eq = S[v+a] == S[prv_v+a];
295 }
296
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 50 → 51 taken 654348 times.
✓ Branch 50 → 52 taken 977565 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 50 → 51 taken 633247 times.
✓ Branch 50 → 52 taken 2056416 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 50 → 51 taken 579182 times.
✓ Branch 50 → 52 taken 485654 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 50 → 51 taken 554191 times.
✓ Branch 50 → 52 taken 1471589 times.
 7412192 if (!eq) {
297 2420968 next_sigma++;
298 2420968 prv_len = len;
299 2420968 prv_v = v;
300 }
301
302 7412192 sa[v>>1] = next_sigma; // purposely leave this 1 large to check != 0
303 }
304 }
305
306
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 54 → 55 taken 18 times.
✓ Branch 54 → 56 taken 93 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 54 → 55 taken 16 times.
✓ Branch 54 → 56 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 54 → 55 taken 12 times.
✓ Branch 54 → 56 taken 61 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 54 → 55 taken 1 time.
✓ Branch 54 → 56 taken 16 times.
 239 if (next_sigma == num_pieces) {
307 47 sa[0] = N;
308 47 memcpy(sa+1, pieces, sizeof(*sa) * num_pieces);
309 } else {
310 192 index_t* next_S = sa_end;
311
312 // Finally, pack the input to the SA
313 {
314
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 60 → 57 taken 1824864 times.
✓ Branch 60 → 61 taken 93 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 60 → 57 taken 3797966 times.
✓ Branch 60 → 61 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 60 → 57 taken 1246916 times.
✓ Branch 60 → 61 taken 61 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 60 → 57 taken 3043448 times.
✓ Branch 60 → 61 taken 16 times.
 9913386 for (int i = (N-1)>>1; i >= 0; i--) {
315 9913194 int v = sa[i];
316
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 57 → 58 taken 1465646 times.
✓ Branch 57 → 59 taken 359218 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 57 → 58 taken 2689479 times.
✓ Branch 57 → 59 taken 1108487 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 57 → 58 taken 917120 times.
✓ Branch 57 → 59 taken 329796 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 57 → 58 taken 2025777 times.
✓ Branch 57 → 59 taken 1017671 times.
 9913194 if (v) *--next_S = v-1;
317 9913194 sa[i] = 0;
318 }
319 }
320
321 192 memset(sa, 0, sizeof(*sa) * (num_pieces+1));
322 192 sais<const index_t*>(num_pieces, next_S, sa, next_sigma, tmp);
323
324 { // Compute the piece start points again and use those to map up the suffix array
325 192 next_S = sa_end;
326 192 index_t c0 = S[N-1], c1 = -1; bool isS = false;
327
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 67 → 63 taken 3649593 times.
✓ Branch 67 → 68 taken 93 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 67 → 63 taken 7595901 times.
✓ Branch 67 → 68 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 67 → 63 taken 2493746 times.
✓ Branch 67 → 68 taken 61 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 67 → 63 taken 6086873 times.
✓ Branch 67 → 68 taken 16 times.
 19826305 for (int i = N-2; i >= 0; i--) {
328 19826113 c1 = c0;
329
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 63 → 64 taken 3985799 times.
✓ Branch 63 → 66 taken 3610102 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 63 → 64 taken 3220991 times.
✓ Branch 63 → 66 taken 2865882 times.
 19826113 c0 = S[i];
330
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 63 → 64 taken 1897136 times.
✓ Branch 63 → 66 taken 1752457 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 63 → 64 taken 3985799 times.
✓ Branch 63 → 66 taken 3610102 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 63 → 64 taken 1319597 times.
✓ Branch 63 → 66 taken 1174149 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 63 → 64 taken 3220991 times.
✓ Branch 63 → 66 taken 2865882 times.
 19826113 if (c0 < c1) {
331 isS = true;
332
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 64 → 65 taken 1465646 times.
✓ Branch 64 → 66 taken 431490 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 64 → 65 taken 2689479 times.
✓ Branch 64 → 66 taken 1296320 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 64 → 65 taken 917120 times.
✓ Branch 64 → 66 taken 402477 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 64 → 65 taken 2025777 times.
✓ Branch 64 → 66 taken 1195214 times.
 10423523 } else if (c0 > c1 && isS) {
333 7098022 isS = false;
334
335 7098022 int v = i+1;
336 7098022 *--next_S = v;
337 }
338 }
339 192 sa[0] = N;
340
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 70 → 69 taken 1465646 times.
✓ Branch 70 → 71 taken 93 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 70 → 69 taken 2689479 times.
✓ Branch 70 → 71 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 70 → 69 taken 917120 times.
✓ Branch 70 → 71 taken 61 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 70 → 69 taken 2025777 times.
✓ Branch 70 → 71 taken 16 times.
 7098214 for (int i = 1; i <= num_pieces; i++) {
341 7098022 sa[i] = next_S[sa[i]];
342 }
343 }
344 }
345
346 // zero everything else
347 239 memset(sa+num_pieces+1, 0, sizeof(*sa) * (N - num_pieces));
348
349 {
350 // Scatter the finished pieces
351 239 build_bucket_end();
352
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 75 → 74 taken 1631913 times.
✓ Branch 75 → 76 taken 111 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 75 → 74 taken 2689663 times.
✓ Branch 75 → 76 taken 38 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 75 → 74 taken 1064836 times.
✓ Branch 75 → 76 taken 73 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 75 → 74 taken 2025780 times.
✓ Branch 75 → 76 taken 17 times.
 7412431 for (int i = num_pieces; i > 0; i--) {
353 7412192 int v = sa[i];
354 7412192 sa[i] = 0;
355
356 7412192 index_t c1 = S[v];
357 7412192 sa[--tmp[c1]] = v;
358 }
359 }
360 }
361
362 // Home stretch! Just finish out with the L-type and then S-type
363 {
364 265 build_bucket_start();
365
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 86 → 78 taken 4155240 times.
✓ Branch 86 → 87 taken 115 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 86 → 78 taken 13584591 times.
✓ Branch 86 → 87 taken 49 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 86 → 78 taken 2942974 times.
✓ Branch 86 → 87 taken 77 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 86 → 78 taken 8550808 times.
✓ Branch 86 → 87 taken 24 times.
 29233878 for (int z = 0; z <= N; z++) {
366 29233613 int v = sa[z];
367
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 78 → 79 taken 2051554 times.
✓ Branch 78 → 80 taken 2103686 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 78 → 79 taken 4502629 times.
✓ Branch 78 → 80 taken 9081962 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 78 → 79 taken 1445080 times.
✓ Branch 78 → 80 taken 1497894 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 78 → 79 taken 3111851 times.
✓ Branch 78 → 80 taken 5438957 times.
 29233613 if (v <= 0) continue;
368 18122499 --v;
369
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 80 → 81 taken 9081935 times.
✓ Branch 80 → 82 taken 27 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 80 → 81 taken 5438944 times.
✓ Branch 80 → 82 taken 13 times.
 18122499 index_t c1 = S[v];
370
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 80 → 81 taken 2103612 times.
✓ Branch 80 → 82 taken 74 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 80 → 81 taken 9081935 times.
✓ Branch 80 → 82 taken 27 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 80 → 81 taken 1497839 times.
✓ Branch 80 → 82 taken 55 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 80 → 81 taken 5438944 times.
✓ Branch 80 → 82 taken 13 times.
 18122499 index_t c0 = v ? S[v-1] : c1; // if v = 0, we don't want to invert
371
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 82 → 83 taken 1631957 times.
✓ Branch 82 → 84 taken 471729 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 82 → 83 taken 2689688 times.
✓ Branch 82 → 84 taken 6392274 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 82 → 83 taken 1064861 times.
✓ Branch 82 → 84 taken 433033 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 82 → 83 taken 2025792 times.
✓ Branch 82 → 84 taken 3413165 times.
 25534797 sa[tmp[c1]++] = (c0 < c1) ? ~v : v;
372 }
373 }
374
375 // This just aggressively overwrites our original scattered pieces with the correct values
376 {
377 265 build_bucket_end();
378
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 98 → 89 taken 4155240 times.
✓ Branch 98 → 99 taken 115 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 98 → 89 taken 13584591 times.
✓ Branch 98 → 99 taken 49 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 98 → 89 taken 2942974 times.
✓ Branch 98 → 99 taken 77 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 98 → 89 taken 8550808 times.
✓ Branch 98 → 99 taken 24 times.
 29233878 for (int z = N; z >= 0; z--) {
379 29233613 int v = sa[z];
380
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 89 → 90 taken 2103801 times.
✓ Branch 89 → 91 taken 2051439 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 89 → 90 taken 9082011 times.
✓ Branch 89 → 91 taken 4502580 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 89 → 90 taken 1497971 times.
✓ Branch 89 → 91 taken 1445003 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 89 → 90 taken 5438981 times.
✓ Branch 89 → 91 taken 3111827 times.
 29233613 if (v >= 0) continue;
381 11110849 sa[z] = v = ~v;
382 11110849 --v;
383
4/4
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 91 → 92 taken 4502558 times.
✓ Branch 91 → 93 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 91 → 92 taken 3111816 times.
✓ Branch 91 → 93 taken 11 times.
 11110849 index_t c1 = S[v];
384
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 91 → 92 taken 2051398 times.
✓ Branch 91 → 93 taken 41 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 91 → 92 taken 4502558 times.
✓ Branch 91 → 93 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 91 → 92 taken 1444981 times.
✓ Branch 91 → 93 taken 22 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 91 → 92 taken 3111816 times.
✓ Branch 91 → 93 taken 11 times.
 11110849 index_t c0 = v ? S[v-1] : c1+1;
385
8/8
void SuffixArrayBase<SuffixArray>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 94 → 95 taken 419482 times.
✓ Branch 94 → 96 taken 1631957 times.
void SuffixArrayBase<SuffixArray>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 94 → 95 taken 1812892 times.
✓ Branch 94 → 96 taken 2689688 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<int const*>(int, int const* const&, int*, int, int*):
✓ Branch 94 → 95 taken 380142 times.
✓ Branch 94 → 96 taken 1064861 times.
void SuffixArrayBase<SuffixArrayLCP>::sais<std::vector<char, std::allocator<char> > >(int, std::vector<char, std::allocator<char> > const&, int*, int, int*):
✓ Branch 94 → 95 taken 1086035 times.
✓ Branch 94 → 96 taken 2025792 times.
 11110849 sa[--tmp[c1]] = (c0 > c1) ? v : ~v;
386 }
387 }
388 }
389
390 74 void build_rank() {
391 74 rank = std::vector<index_t>(N+1);
392
4/4
SuffixArrayBase<SuffixArray>::build_rank():
✓ Branch 7 → 6 taken 13584593 times.
✓ Branch 7 → 8 taken 50 times.
SuffixArrayBase<SuffixArrayLCP>::build_rank():
✓ Branch 7 → 6 taken 8550808 times.
✓ Branch 7 → 8 taken 24 times.
 22135475 for (int i = 0; i <= N; i++) rank[sa[i]] = i;
393 74 }
394 };
395
396
1/1
✓ Branch 2 → 3 taken 50 times.
 150 class SuffixArray : public SuffixArrayBase<SuffixArray> {};
397
398 24 template <typename Self> class SuffixArrayLCPBase : public SuffixArrayBase<Self> {
399 public:
400 using index_t = typename SuffixArrayBase<Self>::index_t;
401 // lcp[i] = lcp(sa[i], sa[i+1])
402 std::vector<index_t> lcp;
403
404 protected:
405 friend SuffixArrayBase<Self>;
406 24 template <typename String> void build(const String& S, index_t sigma) {
407 24 SuffixArrayBase<Self>::build(S, sigma);
408 24 build_lcp(S);
409 24 }
410
411 private:
412 24 template <typename String> void build_lcp(const String& S) {
413 24 int N = this->N;
414 24 const auto& sa = this->sa;
415 24 const auto& rank = this->rank;
416 24 assert(sz(S) == N);
417 24 lcp = std::vector<index_t>(N);
418
2/2
✓ Branch 15 → 8 taken 8550760 times.
✓ Branch 15 → 16 taken 24 times.
 8550784 for (int i = 0, k = 0; i < N - 1; i++) {
419 8550760 int j = sa[rank[i]-1];
420
4/4
✓ Branch 9 → 10 taken 13394756 times.
✓ Branch 9 → 12 taken 3706489 times.
✓ Branch 10 → 11 taken 8550485 times.
✓ Branch 10 → 12 taken 4844271 times.
 17101245 while (k < N - std::max(i, j) && S[i+k] == S[j+k]) k++;
421
2/2
✓ Branch 12 → 13 taken 8550485 times.
✓ Branch 12 → 14 taken 275 times.
 8550760 lcp[rank[i]-1] = k;
422
2/2
✓ Branch 12 → 13 taken 8550485 times.
✓ Branch 12 → 14 taken 275 times.
 8550760 if (k) --k;
423 }
424 24 }
425 };
426
427
1/1
✓ Branch 2 → 3 taken 24 times.
 48 class SuffixArrayLCP : public SuffixArrayLCPBase<SuffixArrayLCP> {};
428
429 template <typename Self> class SuffixArrayRMQBase : public SuffixArrayLCPBase<Self> {
430 public:
431 using index_t = typename SuffixArrayLCPBase<Self>::index_t;
432 RangeMinQuery<std::pair<index_t, index_t>> rmq;
433
434 ✗ index_t get_lcp(index_t a, index_t b) const {
435 ✗ if (a == b) return this->N-a;
436 ✗ a = this->rank[a], b = this->rank[b];
437 ✗ if (a > b) std::swap(a, b);
438 ✗ return rmq.query(a, b-1).first;
439 }
440
441 // Get the split in the suffix tree, using half-open intervals
442 // Returns len, idx
443 ✗ std::pair<index_t, index_t> get_split(index_t l, index_t r) const {
444 ✗ assert(r - l > 1);
445 ✗ return rmq.query(l, r-2);
446 }
447
448 protected:
449 friend SuffixArrayBase<Self>;
450 ✗ template <typename String> void build(const String& S, index_t sigma) {
451 ✗ SuffixArrayLCPBase<Self>::build(S, sigma);
452 ✗ build_rmq();
453 }
454
455 private:
456 ✗ void build_rmq() {
457 ✗ int N = this->N;
458 ✗ const auto& lcp = this->lcp;
459 ✗ std::vector<std::pair<index_t, index_t>> lcp_idx(N);
460 ✗ for (int i = 0; i < N; i++) {
461 ✗ lcp_idx[i] = {lcp[i], i+1};
462 }
463 ✗ rmq = RangeMinQuery<std::pair<index_t, index_t>>(std::move(lcp_idx));
464 }
465 };
466
467 class SuffixArrayRMQ : public SuffixArrayRMQBase<SuffixArrayRMQ> {};
468
469 class PrefixArrayRMQ : private SuffixArrayRMQ {
470 ✗ PrefixArrayRMQ(const SuffixArrayRMQ& sa_) : SuffixArrayRMQ(sa_) {}
471 ✗ PrefixArrayRMQ(SuffixArrayRMQ&& sa_) : SuffixArrayRMQ(std::move(sa_)) {}
472 public:
473 ✗ PrefixArrayRMQ() {}
474 ✗ template <typename String> static PrefixArrayRMQ construct_raw(const String& S, int sigma) {
475 ✗ return PrefixArrayRMQ(SuffixArrayRMQ::construct_raw(String(S.rbegin(), S.rend()), sigma));
476 }
477
478 // TODO: Fill in other constructors
479
480 ✗ int get_lcs(int a, int b) const {
481 ✗ return SuffixArrayRMQ::get_lcp(N - a, N - b);
482 }
483 };
484