B4039 [GESP202409 三级] 回文拼接

chen_zhe · 2024-11-12 20:06:00 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

:::align{center} :::

本题考察字符串和相关函数的使用。

题目问，每个字符串是否由两个长度至少为 2 的回文串前后拼接而成。先简化问题：如何获取这两个字符串呢（先不考虑是不是回文）？

可以枚举开头的字符串长度 i，这样便可以知获得这两个字符串了。截取字符串的常用函数是 substr，用法如下：

• s.substr(pos,len)：从下标 pos 开始，截取长度为 len 的字符串；
• s.substr(pos)：从下标 pos 开始，截取到字符串末。

字符串相关的函数（如大小写转换、字符串搜索、分割、替换等）在 GESP 三级考纲内要求掌握，建议学习并且灵活运用。

下一个问题是判断回文。根据定义，回文字符串指的是从前往后读和从后往前读是一样的字符串。假设字符串 a 是要判断是否回文的字符串，长度为 i。流程就是：判断 a_0 和 a_{i-1} 是否相同，判断 a_1 和 a_{i-2} 是否相同，判断 a_2 和 a_{i-3} 是否相同，以此类推。代码写作如下：

bool flag = true;
for (int j = 0; j < a.length(); j++) {
    if (a[j] != a[a.length() - j - 1])
        flag = false;
}

因此整个代码的参考流程可以写作：

for (int i = 2; i + 1 < s.length(); i++) {
    //枚举开头的字符串长度 i
    string a = s.substr(0, i);
    string b = s.substr(i);
    //判断 a 是否回文，代码略
    //判断 b 是否回文，代码略
    if (flag) {
        cout << "Yes" << endl;//存在一种分割方案
        flag2 = true;//确认已经有解
    }
}