2026 杭电春季联赛-1003-回文串（ABA‘ 是这个回文串的形式） · znzryb
## 题目大意
**题目描述**
给定两个长度均为 $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"}$，是回文串。
1. 选取 $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](/2026/03/20/20260320-e33d77f6)
```cpp
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)$ 的，但是还是这个哈希表还是有点慢，被卡了。
::: 源代码
```cpp
/**
* 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](https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239)
::: 源代码
```cpp
/**
* 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……）