#include<bits/stdc++.h> #define N 60005 usingnamespacestd;
int t, n, nn; char s[N]; int a[N], b[N]; int sa[N], sa2[N], rnk[N], sum[N], key[N], height[N], ST[N][21];
inlineboolcheck(int *num, int aa, int bb, int l){ if (aa + l > n || bb + l > n) returnfalse; //多组数据,一定要加! return num[aa] == num[bb] && num[aa+l] == num[bb+l]; } voidDA(){ int i, j, p, m = 128; for (i = 1; i <= m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[rnk[i]=s[i]]++; for (i = 2; i <= m; i++) sum[i] += sum[i-1]; for (i = n; i; i--) sa[sum[rnk[i]]--] = i; for (j = 1; j <= n; j <<= 1, m = p) { for (p = 0, i = n - j + 1; i <= n; i++) sa2[++p] = i; for (i = 1; i <= n; i++) if (sa[i] - j > 0) sa2[++p] = sa[i] - j; for (i = 1; i <= n; i++) key[i] = rnk[sa2[i]]; for (i = 1; i <= m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[key[i]]++; for (i = 2; i <= m; i++) sum[i] += sum[i-1]; for (i = n; i; i--) sa[sum[key[i]]--] = sa2[i]; for (swap(sa2, rnk), p = 2, rnk[sa[1]] = 1, i = 2; i <= n; i++) { rnk[sa[i]] = check(sa2, sa[i-1], sa[i], j) ? p - 1 : p++; } } }
voidgeth(){ int p = 0; for (int i = 1; i <= n; i++) rnk[sa[i]] = i; for (int i = 1; i <= n; i++) { if (p) p--; int j = sa[rnk[i]-1]; while (s[i+p] == s[j+p] && i + p <= n && j + p <= n) p++; //多组数据,一定要加! height[rnk[i]] = p; } }
voidpreST(){ for (int i = 1; i <= n; i++) ST[i][0] = height[i]; for (int l = 1; (1 << l) <= n; l++) { for (int i = 1; i + (1<<l) - 1 <= n; i++) { ST[i][l] = min(ST[i][l-1], ST[i+(1<<(l-1))][l-1]); } } }
inlineintQST(int x, int y){ if (x > y) swap(x, y); x++; int l = log2(y - x + 1); return min(ST[x][l], ST[y-(1<<l)+1][l]); }
inlineintLCP(int x, int y){ return QST(rnk[x], rnk[y]); } inlineintLCS(int x, int y){ return QST(rnk[n-x+1], rnk[n-y+1]); }
voidSolve(){ for (int l = 1; l * 2 <= nn; l++) { for (int i = 1, j = i + 1; j * l <= nn; i++, j++) { int lcp = min(LCP(i*l, j*l), l), lcs = min(LCS(i*l, j*l), l); if (lcp + lcs - 1 >= l) { a[j*l+l-lcs]++; a[j*l+lcp]--; b[i*l-lcs+1]++; b[i*l-l+lcp+1]--; } } } for (int i = 1; i <= nn; i++) { a[i] += a[i-1]; b[i] += b[i-1]; } longlong ans = 0; for (int i = 1; i < nn; i++) { ans += 1ll * a[i] * b[i+1]; } printf("%lld\n", ans); }
intmain(){ scanf("%d", &t); while (t--) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); scanf("%s", s + 1); n = strlen(s + 1); s[n+1] = '$'; for (int i = n + 2; i <= 2 * n + 1; i++) { s[i] = s[2 * n - i + 2]; } nn = n; n = n * 2 + 1; DA(); geth(); preST(); Solve(); } return0; }