这题质量不错，就是暴力分有点足(hhhhhhhh)，整整有(95)分。
（搞得我写完暴力都不想写正解直接理解思路之后就直接水过去了(QwQ)）
（啊好啦好啦水过去是我的锅啦，我自己出来挨打还不行嘛(QAQ)）
其实就是把(AABB)换成求(AA)然后组合在一块，最后的部分需要推一个奇妙的性质，这里我也不好叙述，详情请见这个大佬的博客。至于求(AA)的方法可以考虑使用后缀数组+(RMQ)实现(O(1))匹配。
（别跟我提哈希听着就来气(TwT)，为什么还可以用(Hash)水啊喂！）
(95pts:)
#include <bits/stdc++.h>
using namespace std;
const int N = 4010;
char s[N];
int n, m, T;
int sa[N], tp[N], rk[N], _rk[N], bin[N], height[N];
void get_height () {
int k = 0;
for (int i = 1; i <= n; ++i) {
if (k != 0) --k;
int j = sa[rk[i] - 1];
while (s[i + k - 1] == s[j + k - 1]) ++k;
height[rk[i]] = k;
}
}
void base_sort () {
for (int i = 1; i <= m; ++i) bin[i] = 0;
for (int i = 1; i <= n; ++i) bin[rk[tp[i]]]++;
for (int i = 1; i <= m; ++i) bin[i] += bin[i - 1];
for (int i = n; i >= 1; --i) sa[bin[rk[tp[i]]]--] = tp[i];
}
void suffix_sort () {
m = 255;
for (int i = 1; i <= n; ++i) {
tp[i] = i, rk[i] = s[i - 1];
}
base_sort ();
for (int w = 1; w <= n; w <<= 1) {
int cnt = 0;
for (int i = n - w + 1; i <= n; ++i) {
tp[++cnt] = i;
}
for (int i = 1; i <= n; ++i) {
if (sa[i] > w) {
tp[++cnt] = sa[i] - w;
}
}
base_sort ();
memcpy (_rk, rk, sizeof (rk));
rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; ++i) {
rk[sa[i]] = (_rk[sa[i]] == _rk[sa[i - 1]]) && (_rk[sa[i] + w] == _rk[sa[i - 1] + w]) ? cnt : ++cnt;
}
if (cnt == n) break;
m = cnt;
}
}
int a[N], b[N], st[N][25];
void get_STlist () {
memset (st, 0, sizeof (st));
for (int i = 1; i <= n; ++i) {
st[i][0] = height[i];
}
int mx = log2 (n);
for (int i = 1; i <= mx; ++i) {
for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
st[j][i] = min (st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
}
int lcp (int x, int y) {
if (x > y) swap (x, y); ++x;
if (x > y) return 0;
int mx = log2 (y - x + 1);
return min (st[x][mx], st[y - (1 << mx) + 1][mx]);
}
void Initialize () {
memset (a, 0, sizeof (a));
memset (b, 0, sizeof (b));
memset (s, 0, sizeof (s));
memset (sa, 0, sizeof (sa));
memset (tp, 0, sizeof (tp));
memset (rk, 0, sizeof (rk));
memset (height, 0, sizeof (height));
scanf ("%s", s);
n = strlen (s);
}
int main () {
cin >> T;
while (T--) {
Initialize ();
suffix_sort ();
get_height ();
get_STlist ();
for (int i = 0; i < n; ++i) { //枚举每一个后缀
for (int l = 1; i + l * 2 - 1 < n; ++l) {
// printf ("lcp (rk[%d] = %d, rk[%d] = %d) = %d
", i, rk[i], i + l, rk[i + l], lcp (rk[i], rk[i + l]))
if (lcp (rk[i + 1], rk[i + l + 1]) >= l) {
a[i + l * 2 - 1]++, b[i]++;
}
}
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans += a[i] * b[i + 1];
}
cout << ans << endl;
}
}
(100pts)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define LOG (15+5)
#define MAXN (30000+5)
int n, c[MAXN], c1[MAXN], c2[MAXN], Log[MAXN];
struct SuffixArray{
char s[MAXN];
int sa[MAXN], h[MAXN][LOG], rank[MAXN];
void init(){
Set(c1, 0); Set(c2, 0);
}
void buildsa(int m='z'){
int *x = c1, *y = c2;
For(i, 1, m) c[i] = 0;
For(i, 1, n) c[x[i]=s[i]]++;
For(i, 1, m) c[i] += c[i-1];
Forr(i, n, 1) sa[c[x[i]]--] = i;
int p;
for(int k = 1; k <= n; k <<= 1){
p = 0;
For(i, n-k+1, n) y[++p] = i;
For(i, 1, n) if(sa[i] > k) y[++p] = sa[i]-k;
For(i, 1, m) c[i] = 0;
For(i, 1, n) c[x[y[i]]]++;
For(i, 1, m) c[i] += c[i-1];
Forr(i, n, 1) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
p = x[sa[1]] = 1;
For(i, 2, n) x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])? p: ++p;
if(p >= n) break;
m = p;
}
}
void getheight(){
For(i, 1, n) rank[sa[i]] = i;
int k = 0, j;
For(i, 1, n){
if(k) k--;
j = sa[rank[i]+1];
if(rank[i] == n) continue;
while(s[i+k] == s[j+k]) k++;
h[rank[i]][0] = k;
}
For(j, 1, 15) For(i, 1, n){
if(i+(1<<(j-1)) > n) break;
h[i][j] = min(h[i][j-1], h[i+(1<<(j-1))][j-1]);
}
}
int LCP(int x, int y){
x = rank[x]; y = rank[y];
if(x > y) swap(x, y);
int k = Log[y-x];
return min(h[x][k], h[y-(1<<k)][k]);
}
}A, B;
int st[MAXN], en[MAXN];
int main(){
For(i, 2, MAXN-1) Log[i] = Log[i>>1]+1;
int T;
scanf("%d", &T);
while(T--){
A.init(); B.init();
Set(st, 0); Set(en, 0);
scanf("%s", A.s+1);
n = strlen(A.s+1);
For(i, 1, n) B.s[i] = A.s[n-i+1];
A.buildsa(); A.getheight();
B.buildsa(); B.getheight();
int j, x, y, t;
For(L, 1, n/2){
for(int i=L, j=i+L; j <= n; i+=L,j+=L){
x = min(A.LCP(i,j), L), y = min(B.LCP(n-(i-1)+1, n-(j-1)+1), L-1);
t = x+y-L+1;
if(x+y >= L){
st[i-y]++; st[i-y+t]--;
en[j+x-t]++; en[j+x]--;
}
}
}
For(i, 1, n) st[i]+=st[i-1], en[i]+=en[i-1];
LL ans = 0;
For(i, 1, n) ans += 1LL*en[i]*st[i+1];
printf("%lld
", ans);
}
return 0;
}