| 4 | struct suffix_array { |
| 5 | string s; int n; vvi P; vector<entry> L; vi idx; |
| 6 | suffix_array(string _s) : s(_s), n(size(s)) { |
| 7 | L = vector<entry>(n), P.push_back(vi(n)), idx = vi(n); |
| 8 | rep(i,0,n) P[0][i] = s[i]; |
| 9 | for (int stp = 1, cnt = 1; cnt >> 1 < n; stp++, cnt <<= 1){ |
| 10 | P.push_back(vi(n)); |
| 11 | rep(i,0,n) |
| 12 | L[L[i].p = i].nr = ii(P[stp - 1][i], |
| 13 | i + cnt < n ? P[stp - 1][i + cnt] : -1); |
| 14 | sort(L.begin(), L.end()); |
| 15 | rep(i,0,n) |
| 16 | P[stp][L[i].p] = i > 0 && |
| 17 | L[i].nr == L[i - 1].nr ? P[stp][L[i - 1].p] : i; } |
| 18 | rep(i,0,n) idx[P[(int)size(P) - 1][i]] = i; } |
| 19 | int lcp(int x, int y) { |
| 20 | int res = 0; |
| 21 | if (x == y) return n - x; |