occurrences of s[p, ..., p + len - 1]
| 163 | } |
| 164 | // occurrences of s[p, ..., p + len - 1] |
| 165 | pair<int, int> find_occurrence(int p, int len) { |
| 166 | p = rank[p]; |
| 167 | pair<int, int> ans = {p, p}; |
| 168 | int l = 0, r = p - 1; |
| 169 | while (l <= r) { |
| 170 | int mid = l + r >> 1; |
| 171 | if (query(mid, p - 1) >= len) ans.first = mid, r = mid - 1; |
| 172 | else l = mid + 1; |
| 173 | } |
| 174 | l = p + 1, r = n - 1; |
| 175 | while (l <= r) { |
| 176 | int mid = l + r >> 1; |
| 177 | if (query(p, mid - 1) >= len) ans.second = mid, l = mid + 1; |
| 178 | else r = mid - 1; |
| 179 | } |
| 180 | return ans; |
| 181 | } |
| 182 | |
| 183 | }; |
| 184 |