G3012 [GESP202409 三级] 回文拼接 题解

知识点：字符串、枚举分割、回文判断。

解题思路

枚举切分点，使左右长度都至少2，用双指针分别检查前缀和后缀是否回文。存在同时为回文的切分即输出Yes。

为什么正确

所有符合长度限制的拼接位置都已枚举，双指针相等条件精确判定每段回文。

易错点

两段都必须至少有2个字符；不能只检查原串整体是否回文。

复杂度

每组时间O(L²)，空间O(L)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    while(n--) {
        string s;
        cin>>s;
        auto pal=[&](int l,int h) {
            while(l<h)if(s[l++]!=s[h--])return false;
            return true;
        }
        ;
        bool ok=false;
        for(int i=2;i<=(int)s.size()-2;i++)if(pal(0,i-1)&&pal(i,s.size()-1))ok=true;
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。