优秀的拆分「NOI2016」

#include <bits/stdc++.h>
#define N 60005
using namespace std;

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]; 

inline bool check(int *num, int aa, int bb, int l) {
	if (aa + l > n || bb + l > n) return false; //多组数据，一定要加！
	return num[aa] == num[bb] && num[aa+l] == num[bb+l];
}
 
void DA() {
	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++;
		}
	} 
}

void geth() {
	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;
	}
}

void preST() {
	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]);
		}
	}
} 

inline int QST(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]);
}

inline int LCP(int x, int y) { return QST(rnk[x], rnk[y]); }
inline int LCS(int x, int y) { return QST(rnk[n-x+1], rnk[n-y+1]); }

void Solve() {
	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];
	}
	long long ans = 0;
	for (int i = 1; i < nn; i++) {
		ans += 1ll * a[i] * b[i+1];
	}
	printf("%lld\n", ans);
} 

int main() {
	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();
	}
	return 0;
}