1 条题解
-
1
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <map> using namespace std; inline int gi() { register int data = 0, w = 1; register char ch = 0; while (!isdigit(ch) && ch != '-') ch = getchar(); if (ch == '-') w = -1, ch = getchar(); while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); return w * data; } const int MAX_N = 3e4 + 5; char a[MAX_N]; int N, lg[MAX_N], f[MAX_N], g[MAX_N]; struct SuffixArray { int sa[MAX_N], rnk[MAX_N], lcp[MAX_N]; void buildSA() { #define cmp(i, j, k) (y[i] == y[j] && y[i + k] == y[j + k]) static int x[MAX_N], y[MAX_N], bln[MAX_N]; memset(sa, 0, sizeof(sa)); memset(rnk, 0, sizeof(rnk)); memset(lcp, 0, sizeof(lcp)); memset(x, 0, sizeof(x)); memset(y, 0, sizeof(y)); memset(bln, 0, sizeof(bln)); int M = 122; for (int i = 1; i <= N; i++) bln[x[i] = a[i]]++; for (int i = 1; i <= M; i++) bln[i] += bln[i - 1]; for (int i = N; i >= 1; i--) sa[bln[x[i]]--] = i; for (int k = 1; k <= N; k <<= 1) { int p = 0; for (int i = 0; i <= M; i++) y[i] = 0; for (int i = N - k + 1; i <= N; i++) y[++p] = i; for (int i = 1; i <= N; i++) if (sa[i] > k) y[++p] = sa[i] - k; for (int i = 0; i <= M; i++) bln[i] = 0; for (int i = 1; i <= N; i++) bln[x[y[i]]]++; for (int i = 1; i <= M; i++) bln[i] += bln[i - 1]; for (int i = N; i >= 1; i--) sa[bln[x[y[i]]]--] = y[i]; swap(x, y); x[sa[1]] = p = 1; for (int i = 2; i <= N; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p; if (p >= N) break; M = p; } for (int i = 1; i <= N; i++) rnk[sa[i]] = i; for (int i = 1, j = 0; i <= N; i++) { if (j) j--; while (a[i + j] == a[sa[rnk[i] - 1] + j]) ++j; lcp[rnk[i]] = j; } } int st[16][MAX_N]; void buildST() { memset(st, 63, sizeof(st)); for (int i = 1; i <= N; i++) st[0][i] = lcp[i]; for (int i = 1; i <= 15; i++) for (int j = 1; j <= N; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } int query(int l, int r) { int _l = l, _r = r; l = min(rnk[_l], rnk[_r]) + 1, r = max(rnk[_l], rnk[_r]); int t = lg[r - l + 1]; return min(st[t][l], st[t][r - (1 << t) + 1]); } } A, B; void Sol() { scanf("%s", a + 1); N = strlen(a + 1); A.buildSA(), A.buildST(); reverse(&a[1], &a[N + 1]); B.buildSA(), B.buildST(); memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); for (int Len = 1; Len <= N / 2; Len++) { for (int i = Len, j = i + Len; j <= N; i += Len, j += Len) { int Lcp = min(A.query(i, j), Len), Lcs = min(B.query(N - i + 2, N - j + 2), Len - 1); int t = Lcp + Lcs - Len + 1; if (Lcp + Lcs >= Len) { g[i - Lcs]++, g[i - Lcs + t]--; f[j + Lcp - t]++, f[j + Lcp]--; } } } for (int i = 1; i <= N; i++) f[i] += f[i - 1], g[i] += g[i - 1]; long long ans = 0; for (int i = 1; i < N; i++) ans += 1ll * f[i] * g[i + 1]; printf("%lld\n", ans); } int main () { #ifndef ONLINE_JUDGE freopen("cpp.in", "r", stdin); #endif for (int i = 2; i <= 30000; i++) lg[i] = lg[i >> 1] + 1; int T; scanf("%d", &T); while (T--) Sol(); return 0; }
- 1
信息
- ID
- 219
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 4
- 已通过
- 4
- 上传者