【程序设计训练】回文串

骑猪看日落 2022-11-28 00:56 120阅读 0赞

> 个人思路仅供参考，如有不足欢迎交流。

## 【问题描述】 ##

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。给你一个字符串，问最少在字符串尾添加多少字符，可以使得字符串变为回文串。

## 【输入格式】 ##

有多组测试数据。

每组测试数据第一行是一个正整数N，表示字符串长度，接下来一行是长度为N的字符串，字符串中只有小写字母。

N=0表示输入结束，并且不需要处理。

40%的数列元素个数N 1 ≤ N≤ 100；

30%的数列元素个数N 1 ≤ N≤ 1000；

20%的数列元素个数N 1 ≤ N≤ 10000；

10%的数列元素个数N 1 ≤ N≤ 100000；

## 【输出格式】 ##

对于每组测试数据，输出一个非负整数：添加最少的字符数，可以使得字符串变为回文串。

## 【样例输入】 ##

3
    aba
    4
    aaac
    0

## 【样例输出】 ##

0
    3

## 【提交代码】 ##

（10/10分，C++）

//57.回文串
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        
        int n;//字符串长度
        string orgn, revr;//origin原字符串，reverse反转后的字符串
        string temp;//在原字符串末尾加字符后的字符串
        int t_len;//temp的长度
        while (cin >> n && n != 0)
        {
        
            cin >> orgn;
            revr.assign(orgn.rbegin(), orgn.rend());//反转
            if (revr == orgn)//本来就是回文串
            {
        
                cout << 0 << endl;
            }
            else
            {
        
                for (int i = 1;i < n;i++)//从加1个字符开始，直到加n-1个
                {
        
                    bool flag = true;//true加i个字符可以，false不可以
                    temp = orgn + revr.substr(n - i);//原字符串+反转字符串末尾i个字符，如aaac，i=1时就在末尾加一个c
                    //string substr(int pos = 0,int n ) const;
                    //从pos开始截取n个字符，n不填则截取到字符串的末尾
                    t_len = temp.length();
    
                    for (int j = 0;j < t_len / 2;j++)
                    {
        
                        if (temp[j] != temp[t_len - 1 - j])
                        {
        
                            flag = false;
                            break;
                        }
                    }
                    if (flag == true)
                    {
        
                        cout << i << endl;
                        break;
                    }
                }
            }
        }
        return 0;
    }