蒟蒻最近学了字符串hash，把时间复杂度降到了$O(Tn^4)$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;
const int N = 5e3 + 5, P = 129, MOD = 1e9 + 7;
char s[N];
ll hashs[N], Pmod[N] = {1};
bool flag[N][N];
int lens;

ll gethash(int sta, int end)
{
	return ((hashs[end] - hashs[sta - 1] * Pmod[end - sta + 1]) % MOD + MOD) % MOD;
}

int main()
{
	int T;
	cin >> T;
	for (int i = 1; i <= N; i++) Pmod[i] = (Pmod[i - 1] * P) % MOD;
	while (T--)
	{
		scanf("%s", s + 1);
		lens = strlen(s + 1);
		for (int i = 1; i <= lens; i++)
			hashs[i] = (hashs[i - 1] * P + s[i] + 1) % MOD;
		for (int i = 1; i <= lens; i++)
		{
			for (int j = 1; i + 2 * j - 1 <= lens; j++)
			{
				ll s1 = gethash(i, i + j - 1);
				ll s2 = gethash(i + j, i + 2 * j - 1);
				if (s1 == s2)
				{
					for (int k = 1; i + 2 * j + k - 1 <= lens; k++)
					{
						ll s3 = gethash(i + 2 * j, i + 2 * j + k - 1);
						for (int l = 1; i + 3 * j + 2 * k + l - 1 <= lens; l++)
						{
							ll s5 = gethash(i + 2 * j + k + l, i + 3 * j + k + l - 1);
							ll s6 = gethash(i + 3 * j + k + l, i + 3 * j + 2 * k + l - 1);
							if (s2 == s5 && s3 == s6)
							{
								// printf("s1 : %d %d ~ %d\n", s1, i, i + j - 1);
								// printf("s2 : %d %d ~ %d\n", s2, i + j, i + 2 * j - 1);
								// printf("s3 : %d %d ~ %d\n", s3, i + 2 * j, i + 2 * j + k - 1);
								// printf("s5 : %d %d ~ %d\n", s5, i + 2 * j + k + l, i + 3 * j + k + l - 1);
								// printf("s6 : %d %d ~ %d\n", s6, i + 3 * j + k + l, i + 3 * j + 2 * k + l - 1);
								flag[i][i + 3 * j + 2 * k + l - 1] = 1;
							}
						}
					}
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= lens; i++)
			for (int j = i + 1; j <= lens; j++)
				if (flag[i][j])
				{
					// cout << i << " " << j << endl;
					ans++;
				}
		cout << ans << endl;
	}
    return 0;
}