【牛客网】：统计回文

题目描述

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有 对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符 串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新 串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。 例如： A = “aba”，B = “b”。这里有4种把B插入A的办法：

在A的第一个字母之前: “baba” 不是回文在第一个字母‘a’之后: “abba” 是回文在字母‘b’之后: “abba” 是回文在第二个字母’a’之后 “abab” 不是回文 所以满足条件的答案为2 输入描述： 每组输入数据共两行。 第一行为字符串A 第二行为字符串B 字符串长度均小于100且只包含小写字母 输出描述： 输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数

题目链接：

示例

输入: aba b 输出: 2

解题思路

本题使用暴力求解方式计算即可，遍历s1，将s2 insert进入str1的每个位置，判断是否是回文，是就 ++count；需要注意的是这里不能 str1.insert(i, str2)，这样的话str1改变了，判断下一个位置就不对了。所 以每次使用str1拷贝构造一个str，然后str.insert(i, str2)，再判断即可。

完整代码

#include <iostream> #include <string> using namespace std; bool HuiWen(const string &s) //验证是否回文串 { size_t begin = 0; size_t end = s.size() - 1; while (begin<end) { if (s[begin] != s[end]) return false; ++begin; ++end; } return true; } int main() { string s1, s2; getline(cin, s1); getline(cin, s2); size_t count = 0; for (size_t i = 0; i<s1.size(); ++i) { string s = s1; //s用于插入后判断 s.insert(i, s2); if (HuiWen(s)) ++count; } cout << count << endl; return 0; }