| 12 | namespace internal { |
| 13 | |
| 14 | std::vector<int> sa_naive(const std::vector<int>& s) { |
| 15 | int n = int(s.size()); |
| 16 | std::vector<int> sa(n); |
| 17 | std::iota(sa.begin(), sa.end(), 0); |
| 18 | std::sort(sa.begin(), sa.end(), [&](int l, int r) { |
| 19 | if (l == r) return false; |
| 20 | while (l < n && r < n) { |
| 21 | if (s[l] != s[r]) return s[l] < s[r]; |
| 22 | l++; |
| 23 | r++; |
| 24 | } |
| 25 | return l == n; |
| 26 | }); |
| 27 | return sa; |
| 28 | } |
| 29 | |
| 30 | std::vector<int> sa_doubling(const std::vector<int>& s) { |
| 31 | int n = int(s.size()); |