唉，我太弱了，什么都不会，连暴力都想不到，唉，我太弱啦！
考虑暴力法，可以枚举一个中间点，左边是 AA，右边是 BB，显然一个中间点对答案的贡献为左边 AA 的个数乘以右边 BB 的个数。考虑用哈希，则我们立马得到一个时间复杂度为 O(n2) O ( n 2 ) 的算法。这样就有了 95 95 分……唉，这个我都没有秒杀，我太弱啦！
如果我们想要基于以上做法进行改进，显然我们的任务变成了找 AA 型字符串出现的位置，如果找到了问题就解决了。但是我太弱了，什么都不会，所以凉了。
唉，我太弱了，基础不牢，地动山摇，要用到后缀数组处理重复子串的东西，但是那个东西我正好弃掉了，还是找个时间学了来再看吧……
先盗一张经典的图：
什么意思呢？这张图讲述的其实是后缀数组解决重复子串问题的通用方法。
我们先枚举重复子串的长度 L L ，然后我们考虑字符 （称它们为关键点）显然，如果这个重复子串重复了 k k 次，以上字符就会有 个被包含在那个重复子串中，且对于相邻的两个关键点，往前和往后是相同的（因为是重复子串嘛）。
例如：xxxaabbaabbxxx，长度为 4 4 的重复子串为 aabb。我们的关键点将字符串分成了：
xxxa|abba|abbx|xx关键点为 x（0）a（4）a（8）和 x（12）。对于第二个关键点和第三个关键点，它们往后能够匹配长度为 的字符串（abb），往前能匹配长度为 1 1 的字符串（a），拼起来就得到了长度为 的字符串 aabb。
也就是说，我们枚举相邻的关键点，然后向前向后匹配，如果匹配总长度大于等于 k k ，设为 ，相当于我们在此之间找到了一个或多个重复了两次的子串。剩下的部分怎么做应该就明白了，留给你们思考。
枚举长度的时间复杂度是 O(n) O ( n ) 的，匹配（求 LCP）的时间复杂度是 O(1) O ( 1 ) 的（用 RMQ），由于关键点数目为 O(ni) O ( n i ) ，因此总的时间复杂度为 O(nlogn) O ( n log n ) 。
唉，我太弱了，好不容易写了一份过了的代码 QAQ。我的实现细节是：
i
i
从 开始，代表左边的关键点，
j
j
从 开始，代表与
i
i
相邻的右边的关键点，退出条件是 （即访问 str[j] 越界就退出）。向前匹配（Forward）时，从第
i
i
个位置和第 个位置进行匹配。向后匹配（Backward）时，也从第
i
i
个位置和第 个位置进行匹配，这样可以防止越界，最后再相应地减去
1
1
即可。至于那些加一减一的问题，额，OI 基本功，举几个例子看看到底该加几就好了（虽然这个过程很痛苦，但是在 OI 生涯中似乎一直都没有避免）。
另外注意求 LCP 时，是在 SA 上做 RMQ，并且要特判自己和自己求 LCP 的情况！并且在 SA 上是求的 的最小值！（看不懂？又没说这句话是给你看的）
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int maxn = 30005;
int n;
char str[maxn];
#define RunInstance(x) delete new x
struct brute
{
ULL hashVal[maxn];
ULL power[maxn];
brute()
{
power[0] = 1;
for (loop i = 1; i <= n; i++)
power[i] = power[i - 1] * 131;
hashVal[0] = 0;
for (loop i = 1; i <= n; i++)
hashVal[i] = hashVal[i - 1] * 131 + str[i - 1];
LL ans = 0;
for (int i = 2; i <= n - 2; i++)
{
int cnt1 = 0, cnt2 = 0;
for (int l = 1; i - (l << 1) >= 0; l++)
{
if (hashVal[i] - hashVal[i - l] * power[l] ==
hashVal[i - l] - hashVal[i - (l << 1)] * power[l])
cnt1++;
}
for (int l = 1; i + (l << 1) <= n; l++)
{
if (hashVal[i + l] - hashVal[i] * power[l] ==
hashVal[i + (l << 1)] - hashVal[i + l] * power[l])
cnt2++;
}
ans += cnt1 * cnt2;
}
printOut(ans);
}
};
struct work
{
struct SAHelper
{
int SA[maxn];
int Rank[maxn];
int Height[maxn];
void GetSA()
{
static int buf[maxn];
static int x[maxn], y[maxn];
int buf_size = 26;
int *rank = x, *SA_second = y;
for (int i = 0; i < n; i++)
rank[i] = str[i] - 'a';
for (int i = 0; i < buf_size; i++) buf[i] = 0;
for (int i = 0; i < n; i++) buf[rank[i]]++;
for (int i = 1; i < buf_size; i++) buf[i] += buf[i - 1];
for (int i = n - 1; ~i; i--) SA[--buf[rank[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int t = 0;
for (int i = n - k; i < n; i++)
SA_second[t++] = i;
for (int i = 0; i < n; i++)
if (SA[i] >= k) SA_second[t++] = SA[i] - k;
for (int i = 0; i < buf_size; i++) buf[i] = 0;
for (int i = 0; i < n; i++) buf[rank[SA_second[i]]]++;
for (int i = 1; i < buf_size; i++) buf[i] += buf[i - 1];
for (int i = n - 1; ~i; i--) SA[--buf[rank[SA_second[i]]]] = SA_second[i];
int* oldRank = rank;
std::swap(rank, SA_second);
rank[SA[0]] = 0;
t = 1;
for (int i = 1; i < n; i++)
rank[SA[i]] = (oldRank[SA[i]] == oldRank[SA[i - 1]] &&
SA[i] + k < n && SA[i - 1] + k < n &&
oldRank[SA[i] + k] == oldRank[SA[i - 1] + k])
? t - 1 : t++;
if (t >= n) break;
buf_size = t;
}
}
void GetHeight()
{
for (int i = 0; i < n; i++)
Rank[SA[i]] = i;
int same = 0;
for (int i = 0; i < n; i++)
{
if (same) same--;
if (Rank[i])
{
int pre = SA[Rank[i] - 1];
while (i + same < n && pre + same < n &&
str[i + same] == str[pre + same])
same++;
}
else
same = 0;
Height[Rank[i]] = same;
}
}
int k;
int minVal[16][maxn];
int Log[maxn];
void init()
{
for (int i = 0; i < n; i++)
minVal[0][i] = Height[i];
k = 0;
while (1 << (k + 1) < n) k++;
for (int i = 1; i <= k; i++)
for (int j = 0; j + (1 << i) - 1 < n; j++)
minVal[i][j] = std::min(minVal[i - 1][j],
minVal[i - 1][j + (1 << (i - 1))]);
for (register int i = 0; i <= n; i++)
{
register int t = 0;
while (1 << (t + 1) < i) t++;
Log[i] = t;
}
}
int LCP(int a, int b)
{
if (a == b) return n - a;
a = Rank[a];
b = Rank[b];
if (a > b) std::swap(a, b);
a++;
register int length = b - a + 1;
register int t = Log[length];
return std::min(minVal[t][a], minVal[t][b - (1 << t) + 1]);
}
} sa1, sa2;
int Left[maxn], Right[maxn];
work() : Left(), Right()
{
sa1.GetSA();
sa1.GetHeight();
sa1.init();
std::reverse(str, str + n);
sa2.GetSA();
sa2.GetHeight();
sa2.init();
for (int l = 1; l <= (n >> 1); l++)
{
for (int i = 0, j = l; j < n; i += l, j += l)
{
int Forward = std::min(sa1.LCP(i, j), l);
int Backward = std::min(sa2.LCP(n - 1 - i, n - 1 - j), l);
int len = Forward + Backward - l - 1;
if (len >= 0)
{
Left[j + Forward - 1 - len]++;
Left[j + Forward]--;
Right[i - Backward + 1]++;
Right[i - Backward + 1 + len + 1]--;
}
}
}
for (int i = 1; i < n; i++)
Left[i] += Left[i - 1];
for (int i = 1; i < n; i++)
Right[i] += Right[i - 1];
LL ans = 0;
for (int i = 1; i < n - 2; i++)
ans += (LL)Left[i] * Right[i + 1];
printOut(ans);
}
};
void run()
{
int T = readIn();
while (T--)
{
scanf("%s", str);
n = strlen(str);
RunInstance(work);
}
}
int main()
{
run();
return 0;
}