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

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

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

题目要求

题目描述

一个字符串是回文串，当且仅当该字符串从前往后读和从后往前读是一样的，例如，$\texttt{aabaa}$ 和 $\texttt{ccddcc}$ 都是回文串，但 $\texttt{abcd}$ 不是。

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

4
abcd
aabbb
aaac
abcdd

输出 #1

No
Yes
No
No

说明/提示

样例 1 解释

对于第 $1,3,4$ 个字符串，都不是由两个长度至少为 $2$ 的回文串前后拼接而成。 第 $2$ 个字符串由回文串 $\texttt{aa}$ 和 $\texttt{bbb}$ 前后拼接而成，并且两个回文串长度都至少为 $2$。

数据规模与约定

对全部的测试数据，保证 $1 \leq n \leq 10$，且每个字符串的长度均不超过 $100$。

---

题目分析

解题思路

本题的解题思路如下：

1. 输入处理：
   • 读取字符串数量n
   • 对每个字符串，判断其是否可以由两个回文串拼接而成
2. 核心逻辑：
   • 对于每个字符串，遍历所有可能的分割点
   • 将字符串分为两部分，分别判断是否为回文串
   • 判断回文串的方法：使用双指针从两端向中间比较
   • 如果两部分都是回文串且长度都大于等于2，输出”Yes”
   • 否则继续尝试下一个分割点
   • 如果所有分割点都不满足条件，输出”No”

复杂度分析：

• 时间复杂度：$O(n \times l^2)$，其中n是字符串数量，l是字符串长度。对每个字符串需要尝试O(l)个分割点，每次判断回文需要O(l)时间
• 空间复杂度：$O(l)$，需要存储子串

---

示例代码

#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;
        }
    }
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。