| 54 | // Two Efficient Algorithms for Linear Time Suffix Array Construction |
| 55 | template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40> |
| 56 | std::vector<int> sa_is(const std::vector<int>& s, int upper) { |
| 57 | int n = int(s.size()); |
| 58 | if (n == 0) return {}; |
| 59 | if (n == 1) return {0}; |
| 60 | if (n == 2) { |
| 61 | if (s[0] < s[1]) { |
| 62 | return {0, 1}; |
| 63 | } else { |
| 64 | return {1, 0}; |
| 65 | } |
| 66 | } |
| 67 | if (n < THRESHOLD_NAIVE) { |
| 68 | return sa_naive(s); |
| 69 | } |
| 70 | if (n < THRESHOLD_DOUBLING) { |
| 71 | return sa_doubling(s); |
| 72 | } |
| 73 | |
| 74 | std::vector<int> sa(n); |
| 75 | std::vector<bool> ls(n); |
| 76 | for (int i = n - 2; i >= 0; i--) { |
| 77 | ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]); |
| 78 | } |
| 79 | std::vector<int> sum_l(upper + 1), sum_s(upper + 1); |
| 80 | for (int i = 0; i < n; i++) { |
| 81 | if (!ls[i]) { |
| 82 | sum_s[s[i]]++; |
| 83 | } else { |
| 84 | sum_l[s[i] + 1]++; |
| 85 | } |
| 86 | } |
| 87 | for (int i = 0; i <= upper; i++) { |
| 88 | sum_s[i] += sum_l[i]; |
| 89 | if (i < upper) sum_l[i + 1] += sum_s[i]; |
| 90 | } |
| 91 | |
| 92 | auto induce = [&](const std::vector<int>& lms) { |
| 93 | std::fill(sa.begin(), sa.end(), -1); |
| 94 | std::vector<int> buf(upper + 1); |
| 95 | std::copy(sum_s.begin(), sum_s.end(), buf.begin()); |
| 96 | for (auto d : lms) { |
| 97 | if (d == n) continue; |
| 98 | sa[buf[s[d]]++] = d; |
| 99 | } |
| 100 | std::copy(sum_l.begin(), sum_l.end(), buf.begin()); |
| 101 | sa[buf[s[n - 1]]++] = n - 1; |
| 102 | for (int i = 0; i < n; i++) { |
| 103 | int v = sa[i]; |
| 104 | if (v >= 1 && !ls[v - 1]) { |
| 105 | sa[buf[s[v - 1]]++] = v - 1; |
| 106 | } |
| 107 | } |
| 108 | std::copy(sum_l.begin(), sum_l.end(), buf.begin()); |
| 109 | for (int i = n - 1; i >= 0; i--) { |
| 110 | int v = sa[i]; |
| 111 | if (v >= 1 && ls[v - 1]) { |
| 112 | sa[--buf[s[v - 1] + 1]] = v - 1; |
| 113 | } |
no test coverage detected