GESP202409 三级回文拼接

题意分析¶

我们有 $n$ 个仅包含小写字母的字符串，对于每个字符串，需要判断其是否可以被拆分为两个连续的子串，且这两个子串都是长度至少为 2 的回文串。

例如：

aabbb 可拆为 aa 和 bbb，均为长度 $\geq 2$ 的回文串 $\to$ Yes
abcd 无法满足要求 $\to$ No

解题思路¶

核心思路¶

我们要判断字符串 $s$ 是否可以拆分为两个非重叠的子串 $s_1$ 和 $s_2$，满足以下条件：

$s_1 + s_2 = s$
$\text{len}(s_1) \ge 2$
$\text{len}(s_2) \ge 2$
$s_1$ 是回文串
$s_2$ 是回文串

枚举切分点¶

从下标 $i = 2$ 到 $i = n - 2$ 遍历（确保两部分都至少长度为 $2$）其中 n = s.size()：

令 $s_1 = s[0..i-1]$
令 $s_2 = s[i..n-1]$
- 切割字符串可以用 substr() 函数。
- s1 = s.substr(0, i)，从下标 $0$ 往后 $i$ 个字符都属于 $s_1$。
- s2 = s.substr(i)，从下标 $i$ 往后全部的字符都属于 $s_2$。
判断 $s_1$ 和 $s_2$ 是否都是回文串

只要找到一个合法的划分方式即可输出 Yes，否则输出 No。

回文判断方法¶

可以编写一个判断回文的函数，判断一个字符串是否是回文串。

bool check(string s)
{
    int n = s.size();
    for (int i = 0, j = n - 1; i < j; i++, j--)
    {
        if (s[i] != s[j]) return 0;
    }
    return 1;
}

实现步骤¶

读取字符串数量 $t$。
对于每个字符串：
获取长度 $n$，其中 n = s.size()。
枚举切分点 $i$ 从 $2$ 到 $n - 2$，for (int i = 2; i <= n - 2; i++)：
- 提取子串 $s_1 = s[0..i-1]$，$s_2 = s[i..n-1]$
- 分别判断 $s_1$ 和 $s_2$ 是否是回文串
- 若二者均为回文串，则输出 Yes，结束该字符串处理
若所有划分都无效，输出 No
具体可以打标记，最后根据标记变量的值来决定输出。

时间复杂度分析¶

对于每个字符串：
枚举划分点最多 $O(n)$ 次（$n$ 为字符串长度，最大为 $100$）
每次判断两个子串是否为回文串，单次最多 $O(n)$
所以每个字符串的处理时间是 $O(n^2)$，最多 $t=10$ 个字符串，总体复杂度为 $O(t \cdot n^2)$

由于 $t \le 10$ 且 $n \le 100$，总操作量不超过 $10 \cdot 100^2 = 10^4$，可以接受。

总结¶

枚举切分点是本题的核心。
注意子串长度至少为 $2$ 的限制，避免非法划分。
回文判断可以用双指针高效实现，整体复杂度可控。
本题适合练习字符串划分与双指针技术在回文判定中的应用。

GESP202409 三级 回文拼接