求改

代码#20总是TLE，求助

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

typedef long long ll;
const int MAXN = 30010;
const int MOD = 1e9 + 7;
const int BASE = 131;

int g[MAXN], h[MAXN];
ll pre[MAXN], pow_base[MAXN];

void init_hash(const char* s, int n) {
    pre[0] = 0;
    pow_base[0] = 1;
    for (int i = 0; i < n; i++) {
        pre[i + 1] = (pre[i] * BASE + s[i]) % MOD;
        pow_base[i + 1] = (pow_base[i] * BASE) % MOD;
    }
}

inline ll get_hash(int l, int r) {
    return (pre[r] - pre[l] * pow_base[r - l] % MOD + MOD) % MOD;
}

int main() {
    //freopen();
    //freopen();
    int T;
    scanf("%d", &T);

    while (T--) {
        char s[MAXN];
        scanf("%s", s);
        int n = strlen(s);

        memset(g, 0, sizeof(g));
        memset(h, 0, sizeof(h));

        init_hash(s, n);

        for (int len = 1; len <= n / 2; len++) {
            int double_len = 2 * len;
            for (int i = 0; i <= n - double_len; i++) {
                if (get_hash(i, i + len) == get_hash(i + len, i + double_len)) {
                    g[i + double_len]++;
                }
            }
        }

        for (int len = 1; len <= n / 2; len++) {
            int double_len = 2 * len;
            for (int i = 0; i <= n - double_len; i++) {
                if (get_hash(i, i + len) == get_hash(i + len, i + double_len)) {
                    h[i]++;
                }
            }
        }

        ll ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (ll)g[i] * h[i];
        }

        printf("%lld\n", ans);
    }

    return 0;
}