| 2 | bool operator <(const entry &a, const entry &b) { |
| 3 | return a.nr < b.nr; } |
| 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; |
| 22 | for (int k = (int)size(P)-1; k >= 0 && x<n && y<n; k--) |
| 23 | if (P[k][x] == P[k][y]) |
| 24 | x += 1 << k, y += 1 << k, res += 1 << k; |
| 25 | return res; } }; |
| 26 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected