| 30 | } |
| 31 | |
| 32 | vector<int> SA_IS(const vector<int> &vec, int val_range) { |
| 33 | const int n = vec.size(); |
| 34 | vector<int> SA(n), lms_idx; |
| 35 | vector<bool> sl(n); |
| 36 | sl[n - 1] = false; |
| 37 | for (int i = n - 2; i >= 0; --i) { |
| 38 | sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1])); |
| 39 | if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1); |
| 40 | } |
| 41 | reverse(lms_idx.begin(), lms_idx.end()); |
| 42 | induced_sort(vec, val_range, SA, sl, lms_idx); |
| 43 | vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size()); |
| 44 | for (int i = 0, k = 0; i < n; ++i) |
| 45 | if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) { |
| 46 | new_lms_idx[k++] = SA[i]; |
| 47 | } |
| 48 | int cur = 0; |
| 49 | SA[n - 1] = cur; |
| 50 | for (size_t k = 1; k < new_lms_idx.size(); ++k) { |
| 51 | int i = new_lms_idx[k - 1], j = new_lms_idx[k]; |
| 52 | if (vec[i] != vec[j]) { |
| 53 | SA[j] = ++cur; |
| 54 | continue; |
| 55 | } |
| 56 | bool flag = false; |
| 57 | for (int a = i + 1, b = j + 1;; ++a, ++b) { |
| 58 | if (vec[a] != vec[b]) { |
| 59 | flag = true; |
| 60 | break; |
| 61 | } |
| 62 | if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) { |
| 63 | flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1])); |
| 64 | break; |
| 65 | } |
| 66 | } |
| 67 | SA[j] = (flag ? ++cur : cur); |
| 68 | } |
| 69 | for (size_t i = 0; i < lms_idx.size(); ++i) |
| 70 | lms_vec[i] = SA[lms_idx[i]]; |
| 71 | if (cur + 1 < (int)lms_idx.size()) { |
| 72 | auto lms_SA = SA_IS(lms_vec, cur + 1); |
| 73 | for (size_t i = 0; i < lms_idx.size(); ++i) { |
| 74 | new_lms_idx[i] = lms_idx[lms_SA[i]]; |
| 75 | } |
| 76 | } |
| 77 | induced_sort(vec, val_range, SA, sl, new_lms_idx); |
| 78 | return SA; |
| 79 | } |
| 80 | vector<int> suffix_array(const string &s, const int LIM = 128) { |
| 81 | vector<int> vec(s.size() + 1); |
| 82 | copy(begin(s), end(s), begin(vec)); |
no test coverage detected