GESP三级真题 202409-P2·回文拼接:枚举切分 + 双段回文判断完整拆解

这道题，拆两段，两段都要是回文

2024 年 9 月 GESP C++ 三级编程第二题「回文拼接」，是字符串枚举的典型题。

题目问：一个字符串能不能拆成前后两段，两段都是回文串，且每段长度至少为 2？

思路直接：枚举每一个合法的切分点 j，把字符串切成左段和右段，分别判断是不是回文——找到一个合法切分就输出 Yes，全试完都没有就输出 No。

难点在两处：切分点的合法范围，以及怎么判断一段字符串是回文。

题目原文

回文拼接（GESP C++ 三级，2024 年 9 月，编程题 2）

给定 n 个仅含小写字母的字符串。对每个字符串，判断它是否能写成两个回文串的前后拼接，且两段长度都至少为 2。

回文串：从前往后读与从后往前读完全相同的非空字符串。

输入格式：

• 第一行一个正整数 n，表示字符串个数
• 接下来 n 行，每行一个仅含小写字母的字符串

输出格式：

• 对每个字符串输出一行： Yes 或 No

样例输入：

4
abcd
aabbb
aaac
abcdd

样例输出：

No
Yes
No
No

说明： aabbb 可拆为 aa 与 bbb，均为回文且长度均不少于 2；其余在同样规则下不成立。

数据范围： 1 ≤ n ≤ 10；字符串仅含小写字母。

家长速览

本篇核心：枚举切分点 j（从 2 到 m-2），用 s.substr 取左右两段，用 reverse 翻转后比较判断是否回文。堵点一：j 的范围是 2≤j≤m-2，保证两段各至少 2 个字符。堵点二： substr(0,j) 取前 j 个字符， substr(j,m-j) 取后 m-j 个字符，下标别搞混。堵点三：回文判断用翻转比较——复制一份、reverse、再与原串比较。

第一步：读懂题，手算样例

样例：aabbb（长度 m=5）

合法切分点 j 的范围：j 从 2 到 m-2=3，即 j ∈ {2, 3}。

j=2 时两段都是回文，找到了，输出 Yes。

样例：abcdd（长度 m=5）

全部切分点都不满足，输出 No。

为什么 aaac 也是 No？

j=3 时右段 c 长度为 1，不满足「至少为 2」的要求，不合法。输出 No。

第二步：框架——枚举切分点

读入 n
循环 n 次：
读入字符串 s，设长度为 m
    found =0
对 j 从2到 m-2：
        s1 = s 的前 j 个字符
        s2 = s 的后 m-j 个字符
如果 s1 是回文且 s2 是回文：
            found =1，break
输出Yes或No

为什么 j 从 2 开始，到 m-2 结束？

• j 是左段长度，左段至少 2 个字符 → j ≥ 2
• 右段长度 = m - j，右段至少 2 个字符 → m - j ≥ 2 → j ≤ m - 2
• 所以合法范围是 2≤j≤m-2

第三步：关键细节

细节一： substr 怎么用

string s1 = s.substr(0, j);// 从位置 0 开始，取 j 个字符 = 前 j 个
string s2 = s.substr(j, m - j);// 从位置 j 开始，取 m-j 个字符 = 后 m-j 个

两个参数：起始位置、取多少个。别写成 substr(j,m)，那样会取到越界。

细节二：回文判断用 reverse 翻转比较

string t1 = s1;
reverse(t1.begin(), t1.end());// t1 变成 s1 的倒序
if(t1 == s1){/* s1 是回文 */}

先复制一份（ t1=s1），再 reverse，再与原串比较。不要直接 reverse(s1)，那样原串就被改掉了。

细节三：j 的边界要严格，m < 4 时没有合法切分点

如果字符串长度 m < 4，则 m-2 < 2， for(j=2;j<=m-2;j++) 的循环一次也不进入，直接输出 No。这是正确行为，不需要特判。

第四步：完整代码

#include<bits/stdc++.h>
usingnamespace std;
int main(){
int n;
    cin >> n;
for(int i =0; i < n; i++){
        string s;
        cin >> s;
int m =(int)s.size();
int found =0;
for(int j =2; j <= m -2; j++){
            string s1 = s.substr(0, j);
            string s2 = s.substr(j, m - j);
            string t1 = s1, t2 = s2;
            reverse(t1.begin(), t1.end());
            reverse(t2.begin(), t2.end());
if(t1 == s1 && t2 == s2){
                found =1;
break;
}
}
if(found){
            cout <<"Yes\n";
}else{
            cout <<"No\n";
}
}
return0;
}

动手填一填：程序填空

#include<bits/stdc++.h>
usingnamespace std;
int main(){
int n;
    cin >> n;
for(int i =0; i < n; i++){
        string s;
        cin >> s;
int m =(int)s.size();
int found =0;
for(int j = ___________; j <= ___________; j++){// ① 切分点范围
            string s1 = s.substr(0, j);
            string s2 = s.substr(___________, m - j);// ② 右段起始位置
            string t1 = s1, t2 = s2;
            reverse(t1.begin(), t1.end());
            reverse(t2.begin(), t2.end());
if(t1 == s1 && t2 == s2){ found =1;break;}
}
if(found) cout <<"Yes\n";
else cout <<"No\n";
}
return0;
}

这道题考察的核心能力

小结

「回文拼接」的框架是枚举切分点 + 双段回文判断。

记住这两个关键点：

for(int j =2; j <= m -2; j++)// 两端各至少 2 个字符
string t1 = s1; reverse(t1.begin(), t1.end());// 复制再翻转，不改原串

与上一篇「二进制回文串」对比：数字回文用 while 逐位提取，字符串回文用 reverse 翻转比较——一数一串，两种写法都要熟练。