1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
| #include <cstdio> #include <cstring> #include <algorithm> using namespace std; template <class Type> void read(Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') c == '-' && (flag = true); x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0'; if (flag) x = ~x + 1; } template <class Type, class ...rest> void read(Type &x, rest &...y) { read(x), read(y...); } template <class Type> void write(Type x) { if (x < 0) putchar('-'), x = ~x + 1; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 5e5 + 10; char s[N]; int pre[N], nxt[N]; int n, m, sa[N], rnk[N], ht[N], x[N], y[N], c[N]; void bucsort () { for (int i = 1; i <= m; ++i) c[i] = 0; for (int i = 1; i <= n; ++i) ++c[x[i]]; for (int i = 2; i <= m; ++i) c[i] += c[i - 1]; for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i]; } void init() { for (int i = 1; i <= n; ++i) x[i] = s[i] - 'a' + 1, y[i] = i, sa[i] = 0; bucsort(); for (int k = 1; k <= n; k <<= 1) { int cnt = 0; for (int i = n - k + 1; i <= n; i++) y[++cnt] = i; for (int i = 1; i <= n; i++) if (sa[i] > k) y[++cnt] = sa[i] - k; bucsort(); for (int i = 1; i <= n; i++) y[i] = x[i]; x[sa[1]] = cnt = 1; for (int i = 2; i <= n; i++) x[sa[i]] = cnt += (y[sa[i]] ^ y[sa[i - 1]] || y[sa[i] + k] ^ y[sa[i - 1] + k]); if (cnt == n) break; m = cnt; } for (int i = 1; i <= n; i++) rnk[sa[i]] = i; for (int i = 1, cur = 0; i <= n; i++) { int j = sa[rnk[i] - 1]; if (cur) --cur; while (s[i + cur] == s[j + cur]) cur++; ht[i] = cur; } } void del (int x) { int l = pre[x], r = nxt[x]; ht[r] = min(ht[r], ht[x]); pre[r] = l, nxt[l] = r; } int main () { int T; read(T); while (T--) { scanf("%s", s + 1); n = strlen(s + 1), m = 26; if (n == 1) { puts("0"); continue; } init(); pre[sa[1]] = nxt[sa[n]] = 0; for (int i = 2; i <= n; ++i) pre[sa[i]] = sa[i - 1]; for (int i = 1; i < n; ++i) nxt[sa[i]] = sa[i + 1]; int t = 1, l = 1, r = n; while (t <= n) { if (max(ht[l], ht[nxt[l]]) < t) del(l++); if (l > r) break; ++t; del(r--); } write(t - 1), puts(""); } return 0; }
|
Gitalk 加载中 ...