2026 杭电春季联赛-1003-回文串

题目大意

题目描述
给定两个长度均为 $n$ 的小写字母字符串 $S$ 和 $T$。
你需要在 $S$ 中选取一个子串 $S'$，在 $T$ 中选取一个子串 $T'$（空串不算作子串），并将 $T'$ 拼接在 $S'$ 的后面组成一个新的字符串。
求共有多少种选取方式，使得拼接后的新字符串是一个回文串。
注：选取方式由子串在原串中的起始和终止位置决定；回文串指正读和反读都相同的字符串。

输入格式
第一行输入一个整数表示测试组数 $T$（$T \le 10$）。
接下来每组数据输入两行，分别表示字符串 $S$ 和 $T$。
数据保证两个字符串长度相等且 $n \le 2000$。

输出格式
对于每组数据，输出一行整数，表示能组成回文串的子串选取方案数。

样例

样例输入

2
ab
ac
aba
bba

样例输出

2
15

样例解释
对于第一组样例，$S = \text{"ab"}$，$T = \text{"ac"}$。合法的选取方式共 $2$ 种：

1. 选取 $S[1 \dots 1] = \text{"a"}$ 和 $T[1 \dots 1] = \text{"a"}$，拼接得到 $\text{"aa"}$，是回文串。

2. 选取 $S[1 \dots 2] = \text{"ab"}$ 和 $T[1 \dots 1] = \text{"a"}$，拼接得到 $\text{"aba"}$，是回文串。

对于第二组样例，$S = \text{"aba"}$，$T = \text{"bba"}$。合法的选取方式共 $15$ 种，列举其中几种情况：

• 选取 $S[1 \dots 1] = \text{"a"}$ 和 $T[3 \dots 3] = \text{"a"}$，拼接得到 $\text{"aa"}$。

• 选取 $S[2 \dots 2] = \text{"b"}$ 和 $T[1 \dots 1] = \text{"b"}$，拼接得到 $\text{"bb"}$。

• 选取 $S[2 \dots 2] = \text{"b"}$ 和 $T[2 \dots 2] = \text{"b"}$，拼接得到 $\text{"bb"}$。

• 选取 $S[1 \dots 2] = \text{"ab"}$ 和 $T[2 \dots 3] = \text{"ba"}$，拼接得到 $\text{"abba"}$。

• 选取 $S[1 \dots 3] = \text{"aba"}$ 和 $T[2 \dots 3] = \text{"ba"}$，拼接得到 $\text{"ababa"}$。
  以此类推，满足条件的下标区间组合总共有 $15$ 种。

思路讲解

完全理解 manacher

void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    // 以 i 为起点的这个回文串数量
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
    }
    // 上面是在
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif
		// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            } else {
                lcsuf[i][j] = 0;
            }
            // 加一是因为还有空的情况，即 s 和 rev_t 都不提供 B
            ll add = lcsuf[i][j] * (cntS[i + 1] + cntT[j + 1] + 1);
            ans += add;
        }
    }
    cout << ans << "\n";
}

AC代码

TLE，这个代码是这个 $O(n^2)$ 的，但是还是这个哈希表还是有点慢，被卡了。

源代码

/**
 * Problem: 回文串
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1197&pid=1003
 * Created: 2026-03-21 01:42:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<>, rb_tree_tag,
    tree_order_statistics_node_update>;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();

struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};

struct U {
    using u128 = __uint128_t;
    static constexpr ll MOD = (1ULL << 61) - 1;

    ll v; // always in [0, MOD)

    // --- constructors ---
    U() : v(0) {
    }

    U(ll x) {
        ll t = x % MOD;
        if (t < 0) t += MOD;
        v = (ll) t;
    }

    // explicit U(ull x) {
    //     ll s = (x & MOD) + (x >> 61);
    //     if (s >= MOD) s -= MOD;
    //     v = s;
    // }

    // --- core ops ---
    static inline ll add(ll a, ll b) {
        ll s = a + b;
        if (s >= MOD) s -= MOD;
        return s;
    }

    static inline ll sub(ll a, ll b) {
        return (a >= b) ? (a - b) : (a + MOD - b);
    }

    static inline ll mul(ll a, ll b) {
        u128 t = (u128) a * b; // < 2^122
        ll s = ll(t & MOD) + ll(t >> 61); // 1-step fold
        if (s >= MOD) s -= MOD; // at most one subtract needed
        return s;
    }

    // --- operator overloads ---
    U &operator+=(const U &o) {
        v = add(v, o.v);
        return *this;
    }

    U &operator-=(const U &o) {
        v = sub(v, o.v);
        return *this;
    }

    U &operator*=(const U &o) {
        v = mul(v, o.v);
        return *this;
    }

    friend U operator+(U a, const U &b) {
        a += b;
        return a;
    }

    friend U operator-(U a, const U &b) {
        a -= b;
        return a;
    }

    friend U operator*(U a, const U &b) {
        a *= b;
        return a;
    }

    friend bool operator==(const U &a, const U &b) { return a.v == b.v; }
    friend bool operator!=(const U &a, const U &b) { return a.v != b.v; }
    friend bool operator<(const U &a, const U &b) { return a.v < b.v; }
    friend bool operator>(const U &a, const U &b) { return a.v > b.v; }
    friend bool operator<=(const U &a, const U &b) { return a.v <= b.v; }
    friend bool operator>=(const U &a, const U &b) { return a.v >= b.v; }
};

const U base = 131;

// AC https://vjudge.net/solution/65151535 string matching 测试了find函数功能
// 2025/11/4
// AC https://www.luogu.com.cn/record/245201000 测试了这个push，pop，以及增强get鲁棒性。
struct HS {
    // 字符串哈希模版
    vector<U> hs, powBase;
    U hashval;
    ll n;
    string s;
    // 需要注意的是，字符串哈希和数字一样，都是越前面是越高位。
    // 内部采用 0-based 下标，hs[i] 表示 s[0..i] 的哈希值。
    HS(const string &ls) {
        // 使用const 引用才能绑定到常值对象上
        n = SZ(ls);
        s = ls;
        hs.assign(n, 0);
        powBase.assign(n + 1, 0);
        powBase[0] = 1;
        for (ll i = 1; i <= n; ++i) {
            powBase[i] = powBase[i - 1] * base;
        }
        if (n > 0) {
            hs[0] = U(s[0]);
            for (ll i = 1; i < n; ++i) {
                hs[i] = hs[i - 1] * base + U(s[i]);
            }
            hashval = hs[n - 1];
        } else {
            hashval = 0;
        }
    }

    // get(l, r): 返回 s[l..r] 的哈希（0-based, inclusive）
    // 函数有一定鲁棒性，即使遇到超界问题也能自动纠正
    U get(ll l, ll r) {
        if (n == 0) return 0;
        l = max(0ll, l);
        r = min(n - 1, r);
        if (l > r) return 0;
        if (l == 0) return hs[r];
        return hs[r] - hs[l - 1] * powBase[r - l + 1];
    }

    // get(l): 返回 s[l..n-1] 的哈希（0-based）
    U get(ll l) {
        return get(l, n - 1);
    }

    // 返回ls在s中的出现次数
    ll find(const string &ls) {
        U hxfind = 0;
        ll m = SZ(ls);
        if (m == 0) return n + 1;
        if (m > n) return 0;
        for (ll i = 0; i < m; ++i) {
            hxfind = hxfind * base + ls[i];
        }
        ll res = 0;
        for (ll r = m - 1; r < n; ++r) {
            U hx = get(r - m + 1, r);
            if (hx == hxfind) {
                res++;
            }
        }
        return res;
    }

    void pop() {
        if (n == 0) return;
        n--;
        s.pop_back();
        if (n == 0) {
            hs.clear();
            hashval = 0;
            return;
        }
        hs.pop_back();
        hashval = hs.back();
    }

    void push(char c) {
        s.push_back(c);
        if (n == 0) {
            hs.push_back(U(c));
        } else {
            hs.push_back(hs.back() * base + U(c));
        }
        n++;
        hashval = hs.back();
        if (SZ(powBase) <= n) {
            powBase.push_back(powBase.back() * base);
        }
    }
};

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s) {
    int n = SZ(s);
    s = '$' + s + '^';
    vector<ll> p(n + 2);
    ll l = 0, r = 1; // (l,r) 是开区间，其内部是这个回文子串
    for (int i = 1; i <= n; ++i) {
        // 保底半径
        p[i] = min(r - i, p[l + r - i]);
        // 暴力外扩
        while (s[i - p[i]] == s[i + p[i]]) {
            // 因为有哨兵，永不越界
            p[i]++;
        }
        if (i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<ll>(p.begin() + 1, p.end() - 1);
}

vector<ll> manacher(const string &s) {
    string t;
    for (auto c: s) {
        t += '#'; // 千万不要    t+='#'+'c'
        t += c;
    }
    t += '#';
    auto res = manacher_odd(t);
    return vector<ll>(res.begin() + 1, res.end() - 1);
}

// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntS[pos - r + 1]++;
        //     cntS[((pos + 1) + r - 1) + 1]--;
        // } else {
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
        // }
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntT[pos - r + 1]++;
        //     cntT[]--;
        // } else {
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
        // }
    }
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif

    HS hash1(s), hash2(rev_t);
    gp_hash_table<ll, ll, chash> hs_cntOcc, hs_cntPal;
    for (int i = 0; i < szt; ++i) {
        for (int j = i; j < szt; ++j) {
            auto hx = hash2.get(i, j).v;
            hs_cntOcc[hx]++;
            hs_cntPal[hx] += cntT[j + 1];
        }
    }
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = i; j < szs; ++j) {
            auto hx = hash1.get(i, j).v;
            ll res = 1;
            res += cntS[j + 1];
            auto itOcc = hs_cntOcc.find(hx);
            auto itPal = hs_cntPal.find(hx);
            if (itOcc != hs_cntOcc.end()) {
                ans += res * itOcc->second;
            }
            if (itPal != hs_cntPal.end()) {
                ans += itPal->second;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*


// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            }
        }
    }
*/

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239

源代码

/**
 * Problem: 回文串
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1197&pid=1003
 * Created: 2026-03-21 01:42:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s) {
    int n = SZ(s);
    s = '$' + s + '^';
    vector<ll> p(n + 2);
    ll l = 0, r = 1; // (l,r) 是开区间，其内部是这个回文子串
    for (int i = 1; i <= n; ++i) {
        // 保底半径
        p[i] = min(r - i, p[l + r - i]);
        // 暴力外扩
        while (s[i - p[i]] == s[i + p[i]]) {
            // 因为有哨兵，永不越界
            p[i]++;
        }
        if (i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<ll>(p.begin() + 1, p.end() - 1);
}

vector<ll> manacher(const string &s) {
    string t;
    for (auto c: s) {
        t += '#'; // 千万不要    t+='#'+'c'
        t += c;
    }
    t += '#';
    auto res = manacher_odd(t);
    return vector<ll>(res.begin() + 1, res.end() - 1);
}

// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntS[pos - r + 1]++;
        //     cntS[((pos + 1) + r - 1) + 1]--;
        // } else {
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
        // }
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntT[pos - r + 1]++;
        //     cntT[]--;
        // } else {
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
        // }
    }
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            } else {
                lcsuf[i][j] = 0;
            }
            ll add = lcsuf[i][j] * (cntS[i + 1] + cntT[j + 1] + 1);
            ans += add;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239

// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            }
        }
    }
*/

心路历程（WA，TLE，MLE……）