【每日一题】统计回文

偏执的太偏执、 2022-12-25 04:54 152阅读 0赞

**题目来源**  
牛客网  
链接：[统计回文][Link 1]

**题目描述**  
“回文串”是一个正读和反读都一样的字符串，比如“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

**解题思路**  
本题是判断是否是回文串的变形题。字符串本身不一定是回文，把第二个字符串插入进去看是否是回文。

使用暴力求解方式，意思就是，将str2插入到str1的每一个位置，然后遍历str1，判断是否回文。**注意**：这里不能直接插入到str1，这样的话str1改变了，判断下一个位置就不对了。所以每次使用str1拷贝构造一个str，然后插入到str中，再判断。

**代码展示**

#include <iostream>
    #include <string>
    using namespace std;
    
    //判断是否是回文
    bool IsCircleText(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 str1,str2;
    	getline(cin,str1);
    	getline(cin,str2);
    	size_t count = 0;
    	for(size_t i = 0;i <= str1.size();++i)
    	{
        
    		string str = str1;
    		str.insert(i,str2);
    		if(IsCircleText(str))
    			++count;
    	}
    	cout << count << endl;
    	return 0;
    }

[Link 1]: https://www.nowcoder.com/practice/9d1559511b3849deaa71b576fa7009dc?tpId=85&&tqId=29842&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking