回文拼接 题解

题目分析

本题要求判断给定的字符串是否能够由两个长度都至少为 2 的回文串前后拼接而成。

• 回文串：正着读和反着读完全一样的字符串，如 aa、aba、abba 等。
• 拼接：将第一个回文串与第二个回文串直接首尾相连，形成一个新的字符串。
• 长度要求：拼接用的两个回文串长度都必须 ≥ 2。

例如，字符串 aabbb 可以拆分成 aa 和 bbb，两者都是回文且长度 ≥ 2，因此满足条件。

我们需要对输入的每一个字符串，判断是否存在这样一种拆分方式。

解题思路

由于数据规模非常小（n ≤ 10，字符串长度 ≤ 100），我们可以直接使用暴力枚举的方法。

对于每个字符串 s，设其长度为 m：

1. 枚举分割点：分割点 j 表示第一个回文串的长度，其取值范围为 2 到 m-2（保证左右两边长度都至少为 2）。
2. 截取子串：
   • 左部分：s1 = s[0, j]
   • 右部分：s2 = s[j, m-j]
3. 判断回文：检查 s1 和 s2 是否都是回文串。判断回文可以直接将字符串反转后与原串比较，或者用双指针对比首尾字符。
4. 如果存在任意一个分割点满足条件，则输出 Yes；否则输出 No。

这种方法虽然简单，但在题目给定的数据范围内完全可行。

算法说明

1. 读入整数 n。
2. 循环处理 n 个字符串，对于每个字符串 s：
   • 获取长度 m = s.size()。
   • 设置标志变量 fl = 0，表示是否找到合法分割。
   • 遍历分割点 j 从 2 到 m-2：
     • 截取子串 s1 和 s2。
     • 构造 s1 的反转串 t1（倒序遍历 s1 拼接）。
     • 构造 s2 的反转串 t2。
     • 若 t1 == s1 且 t2 == s2，则 fl = 1，跳出循环。
   • 根据 fl 的值输出 Yes 或 No。

回文判断的另一种写法（双指针）：

cpp
复制
1bool isPalindrome(string s) {
2    int i = 0, j = s.size() - 1;
3    while (i < j) {
4        if (s[i] != s[j]) return false;
5        i++; j--;
6    }
7    return true;
8}

也可以直接使用 C++ 的 reverse 函数或 string 构造函数生成反转串进行比较。

时间复杂度分析

• 对于每个字符串，枚举的分割点数量为 O(m)，其中 m 是字符串长度。
• 每次分割后检查两个子串的回文性，需要 O(m) 的时间（反转字符串和比较都是 O(子串长度)，总和为 O(m)）。
• 所以单个字符串的处理时间为 O(m²)。
• 总时间复杂度为 O(n × m²)。

在最坏情况下，n=10，m=100，计算量约为 10 × 100² = 100,000，完全可以在 1 秒内轻松运行完成，满足题目要求。

参考代码

根据题目给出的参考代码，我们添加了详细的注释以便理解。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    int n;
6    cin >> n;
7    for (int i = 1; i <= n; i++) {
8        string s;
9        cin >> s;
10        int m = s.length();
11        int fl = 0; // 标记是否找到合法分割，0表示未找到，1表示找到
12
13        // 枚举分割点j，j是第一个回文串的长度
14        // 从2开始，保证第一个串长度>=2
15        // 到m-2结束，保证第二个串长度>=2
16        for (int j = 2; j <= m - 2; j++) {
17            string s1 = s.substr(0, j);     // 截取前j个字符
18            string s2 = s.substr(j, m - j); // 截取剩余字符
19
20            // 构造s1的反转串
21            string t1 = "";
22            for (int k = (int)s1.size() - 1; k >= 0; k--) {
23                t1 += s1[k];
24            }
25
26            // 构造s2的反转串
27            string t2 = "";
28            for (int k = (int)s2.size() - 1; k >= 0; k--) {
29                t2 += s2[k];
30            }
31
32            // 如果两个都是回文串，则标记成功并跳出循环
33            if (t1 == s1 && t2 == s2) {
34                fl = 1;
35                break;
36            }
37        }
38
39        // 根据标记输出结果
40        if (fl)
41            cout << "Yes\n";
42        else
43            cout << "No\n";
44    }
45    return 0;
46}

代码解释

• s.substr(0, j)：从索引 0 开始截取长度为 j 的子串，作为第一个部分。
• s.substr(j, m - j)：从索引 j 开始截取剩余部分，作为第二个部分。
• 内层 for 循环通过从尾到头遍历的方式手动反转字符串，然后与原串比较来判断回文。
• 一旦找到合法的分割，立即设置 fl = 1 并 break 跳出循环，避免多余计算。
• 最后根据 fl 输出 Yes 或 No。

总结

本题主要考察对字符串子串截取和回文判断的基本操作。由于数据范围极小，暴力枚举分割点并逐一验证是最直接、最可靠的解法。读者在解决类似问题时，若数据范围较大，可以考虑优化回文判断（如预处理哈希或马拉车算法），但本题中则完全不需要。