| 10 | return (r[a] == r[b] && r[a + x] == r[b + x]); |
| 11 | } |
| 12 | void suffix_array_DA(int n, int m) { |
| 13 | int *x = X, *y = Y, i, j, k = 0, l; |
| 14 | for (i = 0; i <= max(n, m); i++) buc[i] = 0; |
| 15 | for (i = 0; i < n; i++) buc[x[i] = str[i]]++; |
| 16 | for (i = 1; i < m; i++) buc[i] += buc[i - 1]; |
| 17 | for (i = n - 1; i >= 0; i--) suf[--buc[x[i]]] = i; |
| 18 | for (l = 1, j = 1; j < n; m = j, l <<= 1) { |
| 19 | j = 0; |
| 20 | for (i = n - l; i < n; i++) y[j++] = i; |
| 21 | for (i = 0; i < n; i++) if(suf[i] >= l) y[j++] = suf[i] - l; |
| 22 | for (i = 0; i < m; i++) buc[i] = 0; |
| 23 | for (i = 0; i < n; i++) buc[x[y[i]]]++; |
| 24 | for (i = 1; i < m; i++) buc[i] += buc[i - 1]; |
| 25 | for (i = n - 1; i >= 0; i--) suf[--buc[x[y[i]]]] = y[i]; |
| 26 | for (swap(x, y), x[suf[0]] = 0, i = 1, j = 1; i < n; i++) { |
| 27 | x[suf[i]] = cmp(y, suf[i - 1], suf[i], l) ? j - 1 : j++; |
| 28 | } |
| 29 | } |
| 30 | for (i = 1; i < n; i++) r[suf[i]] = i; |
| 31 | for (i = 0; i < n - 1; high[r[i++]] = k) { |
| 32 | for (k ? k-- : 0, j = suf[r[i] - 1]; str[i + k] == str[j + k]; k++); |
| 33 | } |
| 34 | } |
| 35 | struct SuffixArray { |
| 36 | int n; |
| 37 | vector<int> s; |