题解

思路概述

• 想要把字符串拆成尽可能多的回文段，可以从两端同时“配对”：若某个前缀与某个后缀完全相同，那么它们本身就都是回文（因为左右对称），可以直接计作两个答案；剩下的中间部分继续递归处理即可。
• 因此只需维护两个指针 l、r，以及当前未匹配区间的起止位置 lsti、lstj。每次向内扩张一位，若区间 [lsti, l] 与 [r, lstj] 内容完全相同，就说明左右各找到一个回文片段，答案加 2，并把未匹配区间缩成 (l+1, r-1)。当两指针交错时，若还剩一个字符或长度为 2 的未匹配区间，则它自身也是回文段，答案再加 1。
• 这么做的关键是要在 $O(1)$ 时间判断两段字符串是否相等。由于字符串长度最大可达 $10^6$，使用双哈希维护前缀/后缀值即可做到常数时间比较。

实现细节

• 预处理两个随机模数与底数，预先算好所有幂。对每个字符串分别建立前缀哈希和后缀哈希结构，并提供 getHash(l,r)、getHashRev(l,r) 接口进行比较。
• 主过程双指针推进：每次判断 [lsti, l] 的正向哈希与 [r, lstj] 的反向哈希是否相等，相等时将两侧同时收缩并给答案加 2，若指针相遇则补上中间段。
• 算法对每个字符至多访问常数次，因此可以承受 $10^6$ 的数据规模。

复杂度

哈希预处理为 $O(n)$，双指针扫描同样为 $O(n)$，总体时间复杂度 $O(n)$，额外空间复杂度 $O(n)$。

#include <bits/stdc++.h>


using namespace std;
#define int long long
//int mod = 998244353;

const int N = 1e6 + 5;
const int M = (1 << 13);

const int dx4[4] = {0, 0, 1, 1};
const int dy4[4] = {0, 1, 0, 1};

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int getrand(int l, int r) { return uniform_int_distribution<int>(l, r)(RNG); }

int mul(int a, int b, int mod) { return ((a % mod) * (b % mod)) % mod; }

int add(int a, int b, int mod) { return ((a % mod) + (b % mod)) % mod; }

int sub(int a, int b, int mod) { return ((a % mod) - (b % mod) + mod) % mod; }

int fastexp(int a, int b, int mod) {
    if (not b)
        return 1;
    int ret = fastexp(a, b >> 1, mod);
    return (mul(ret, mul(ret, (b & 1 ? a : 1), mod), mod));
}

const int Z = 2;
const int fammods[4] = {1000000007, 2000000011, 127657753, 987654319};
array<int, Z> bases, mods;
vector<array<int, Z>> pw(N);


void get_rand_mods() {
    random_device rd;
    mt19937_64 mt(rd());
    auto rnd = [&](int l, int r) {
        return uniform_int_distribution<int>(l, r)(mt);
    };

    auto check = [](int x) {
        for (int i = 2; i * i <= x; ++i)
            if (x % i == 0)
                return false;
        return true;
    };

    auto &MOD1 = mods[0];
    auto &MOD2 = mods[1];

    MOD1 = rnd(1e9, 2e9);
    MOD2 = rnd(1e8, 2e9);

    while (!check(MOD1)) MOD1--;
    while (MOD1 == MOD2 || !check(MOD2)) MOD2--;

    mods[0] = MOD1, mods[1] = MOD2;
}


void preHashing() {
    // dh law hast5dm el3ady
    for (int b = 0; b < Z; b++) {
        bases[b] = getrand(300, 503);
//        mods[b] = fammods[getrand(0, 3)];
    }

    //fully random
    get_rand_mods();
    for (int b = 0; b < Z; b++) {
        pw[0][b] = 1;
        for (int i = 1; i < N; i++) {
            pw[i][b] = mul(pw[i - 1][b], bases[b], mods[b]);
        }
    }
}

struct Hash {
    int len;
    vector<array<int, Z>> pref, suff;

    Hash(string &s) {
        len = (int) s.size();
        pref.resize(len + 2);
        suff.resize(len + 2);

        // khlbalk al string zero based w a7na mashyeen one based

        // hash pref
        for (int i = 1; i <= len; i++)
            for (int b = 0; b < Z; b++)
                pref[i][b] = add(mul(pref[i - 1][b], bases[b], mods[b]), ((s[i - 1] - ' ' + 1)), mods[b]);

        // hash suff
        for (int i = len; i >= 0; i--)
            for (int b = 0; b < Z; b++)
                suff[i][b] = add(mul(suff[i + 1][b], bases[b], mods[b]), ((s[i - 1] - ' ' + 1)), mods[b]);
    }

    Hash(vector<int> &v) {
        len = (int) v.size() - 1; // -1 3shan hwa dkhly one-based
        pref.resize(len + 2);
        suff.resize(len + 2);

        // khlbalk al vector dakhl one based

        // hash pref
        for (int i = 1; i <= len; i++)
            for (int b = 0; b < Z; b++)
                pref[i][b] = add(mul(pref[i - 1][b], bases[b], mods[b]), v[i], mods[b]);

        // hash suff
        for (int i = len; i >= 0; i--)
            for (int b = 0; b < Z; b++)
                suff[i][b] = add(mul(suff[i + 1][b], bases[b], mods[b]), v[i], mods[b]);
    }

    array<int, Z> getHash(int l, int r) {
        array<int, Z> ret;
        for (int b = 0; b < Z; b++)
            ret[b] = sub(pref[r][b], mul(pref[l - 1][b], pw[r - l + 1][b], mods[b]), mods[b]);

        return ret;
    }

    array<int, Z> getHashRev(int l, int r) {
        array<int, Z> ret;
        for (int b = 0; b < Z; b++)
            ret[b] = sub(suff[l][b], mul(suff[r + 1][b], pw[r - l + 1][b], mods[b]), mods[b]);

        return ret;
    }

    array<int, Z> getHash() { return getHash(1, len); }

    array<int, Z> getHashRev() { return getHashRev(1, len); }

};

void solve() {


    string s;
    cin >> s;

    int cnt = 0;
    Hash h(s);
    int sz = s.size();
    int i = 1, j = sz;

    int lsti = i, lstj = j;

    while (i <= j) {

        if (h.getHash(lsti, i) == h.getHash(j, lstj)) {
            lsti = i + 1, lstj = j - 1, cnt += 2;
            cnt -= (i == j);
        } else if (i == j or i + 1 == j)
            cnt++;

        i++, j--;
    }

    cout << cnt;


}

signed main() {
#ifdef LOCAL
    freopen("../output.out", "w", stdout);
    freopen("../input.in", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
    preHashing();
    cin >> tc;
    while (tc--) {
        solve();
        if (tc) cout << endl;
    }
    return 0;
}