Tips:可以通过正反哈希值的判断出该子串是否是个回文,也可以通过哈希值O(N)的复杂度进行字符串匹配

const int MAXN = 1e6 + 5e3;
int n;
string s;
ll Hash[5][MAXN], Rhash[5][MAXN];
ll mod[] = {2333333, 1333331, 1000000007, 998244353};
const ll BASE = 131; //要比字符数量多
inline void getHash() {
    for (int i = 0; i <= 3; i++) {
        Hash[i][1] = s[0] % mod[i];
        for (int j = 2; j <= n; j++) {
            Hash[i][j] = ((Hash[i][j - 1] * BASE) + s[j - 1]) % mod[i];
        }
        Rhash[i][n] = s[n - 1] % mod[i];
        for (int j = n - 1; j >= 1; j--) {
            Rhash[i][j] = ((Rhash[i][j + 1] * BASE) + s[j - 1]) % mod[i];
        }
    }
}

auto qpow = [] (ll a, ll b, int op) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)res = res * a % mod[op];
        a = a * a % mod[op];
        b >>= 1;
    }
    return res;
};

auto getHashVal = [](int l, int r, int op) { //正向哈希值(l到r)
    return (Hash[op][r] - Hash[op][l - 1] * qpow(BASE, r - l + 1, op)) % mod[op];
};

auto getRhashVal = [](int l, int r, int op) { //逆向哈希值(l到r)
    return (Rhash[op][l] - Rhash[op][r + 1] * qpow(BASE, r - l + 1, op)) % mod[op];
};