| 212 | // Applications |
| 213 | template <class T> |
| 214 | std::vector<int> lcp_array(const std::vector<T>& s, |
| 215 | const std::vector<int>& sa) { |
| 216 | assert(s.size() == sa.size()); |
| 217 | int n = int(s.size()); |
| 218 | assert(n >= 1); |
| 219 | std::vector<int> rnk(n); |
| 220 | for (int i = 0; i < n; i++) { |
| 221 | assert(0 <= sa[i] && sa[i] < n); |
| 222 | rnk[sa[i]] = i; |
| 223 | } |
| 224 | std::vector<int> lcp(n - 1); |
| 225 | int h = 0; |
| 226 | for (int i = 0; i < n; i++) { |
| 227 | if (h > 0) h--; |
| 228 | if (rnk[i] == 0) continue; |
| 229 | int j = sa[rnk[i] - 1]; |
| 230 | for (; j + h < n && i + h < n; h++) { |
| 231 | if (s[j + h] != s[i + h]) break; |
| 232 | } |
| 233 | lcp[rnk[i] - 1] = h; |
| 234 | } |
| 235 | return lcp; |
| 236 | } |
| 237 | |
| 238 | std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) { |
| 239 | int n = int(s.size()); |