| 144 | return query(l, r - 1); |
| 145 | } |
| 146 | int lower_bound(string &t) { |
| 147 | int l = 0, r = n - 1, k = t.size(), ans = n; |
| 148 | while (l <= r) { |
| 149 | int mid = l + r >> 1; |
| 150 | if (s.substr(sa[mid], min(n - sa[mid], k)) >= t) ans = mid, r = mid - 1; |
| 151 | else l = mid + 1; |
| 152 | } |
| 153 | return ans; |
| 154 | } |
| 155 | int upper_bound(string &t) { |
| 156 | int l = 0, r = n - 1, k = t.size(), ans = n; |
| 157 | while (l <= r) { |