OneCoder Avatar
OneCodercoderli.com · 1022 篇博文
三级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++三级真题 luogu-B4039 [GESP202409 三级] 回文拼接

📅 2025-05-21·✍️ OneCoder·计算中...·⏱️ 7 分钟

GESP三级真题,字符串相关题目,难度★★✮☆☆。

luogu-B4039 [GESP202409 三级] 回文拼接

题目要求

题目描述

一个字符串是回文串,当且仅当该字符串从前往后读和从后往前读是一样的,例如, 和 都是回文串,但 不是。

小杨有 个仅包含小写字母的字符串,他想请你编写程序判断每个字符串是否由两个长度至少为 的回文串前后拼接而成。

输入格式

第一行包含一个正整数 ,代表字符串数量。
接下来 行,每行一个仅包含小写字母的字符串。

输出格式

对于每个字符串输出一行,如果该字符串由两个长度至少为 的回文串前后拼接而成则输出 Yes,否则输出 No。

输入输出样例 #1

输入 #1

CONSOLE5 行
4
abcd
aabbb
aaac
abcdd

输出 #1

CONSOLE4 行
No
Yes
No
No

说明/提示

样例 1 解释

对于第 个字符串,都不是由两个长度至少为 的回文串前后拼接而成。 第 个字符串由回文串 和 前后拼接而成,并且两个回文串长度都至少为 。

数据规模与约定

对全部的测试数据,保证 ,且每个字符串的长度均不超过 。


题目分析

解题思路

本题的解题思路如下:

  1. 输入处理:

    • 读取字符串数量n
    • 对每个字符串,判断其是否可以由两个回文串拼接而成
  2. 核心逻辑:

    • 对于每个字符串,遍历所有可能的分割点
    • 将字符串分为两部分,分别判断是否为回文串
    • 判断回文串的方法:使用双指针从两端向中间比较
    • 如果两部分都是回文串且长度都大于等于2,输出"Yes"
    • 否则继续尝试下一个分割点
    • 如果所有分割点都不满足条件,输出"No"

复杂度分析:

  • 时间复杂度:,其中n是字符串数量,l是字符串长度。对每个字符串需要尝试个分割点,每次判断回文需要时间
  • 空间复杂度:,需要存储子串

示例代码

C++60 行
#include <iostream>

int main() {
    // 读取测试用例数量
    int n;
    std::cin >> n;
    // 处理每个测试用例
    for (int i = 0; i < n; i++) {
        std::string str;
        std::cin >> str;
        // 如果字符串长度小于4,不可能由两个长度至少为2的回文串组成
        if (str.length() < 4) {
            std::cout << "No" << std::endl;
            continue;
        }
        bool flag = true;
        // 遍历所有可能的分割点
        for (int j = 1; j < str.length() - 1; j++) {
            flag = true;
            // 分割字符串为两部分
            std::string f_str = str.substr(0, j);
            std::string s_str = str.substr(j, str.length() - j);
            // 检查第一部分是否为回文串
            int f_b = 0;
            int f_e = f_str.length() - 1;

            while (f_b < f_e) {
                if (f_str[f_b] != f_str[f_e]) {
                    flag = false;
                    break;
                }
                f_b++;
                f_e--;
            }
            // 如果第一部分是回文串,检查第二部分
            if (flag) {
                int s_b = 0;
                int s_e = s_str.length() - 1;
                while (s_b < s_e) {
                    if (s_str[s_b] != s_str[s_e]) {
                        flag = false;
                        break;
                    }
                    s_b++;
                    s_e--;
                }
            }
            // 如果两部分都是回文串且长度都大于等于2
            if (flag && f_str.length() >= 2 && s_str.length() >= 2) {
                std::cout << "Yes" << std::endl;
                break;
            }
            flag = false;
        }

        if (!flag) {
            std::cout << "No" << std::endl;
        }
    }
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!