| 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) { |
| 158 | int mid = l + r >> 1; |
| 159 | if (s.substr(sa[mid], min(n - sa[mid], k)) > t) ans = mid, r = mid - 1; |
| 160 | else l = mid + 1; |
| 161 | } |
| 162 | return ans; |
| 163 | } |
| 164 | // occurrences of s[p, ..., p + len - 1] |
| 165 | pair<int, int> find_occurrence(int p, int len) { |
| 166 | p = rank[p]; |