小易爱回文

小易得到了一个仅包含大小写英文字符的字符串,该字符串可能不是回文串。(“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串,“asds”就不是回文串。)

小易可以在字符串尾部加入任意数量的任意字符,使其字符串变成回文串。

现在请你编写一个程序,程序要能计算出小易可以得到的最短回文串。
输入例子1:
noon

输出例子1:
noon

输入例子2:
noo

输出例子2:
noon

输入例子3:
helloworld

输出例子3:
helloworldlrowolleh

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    string res1, res2;
    int n = s.size();
    
    for (int i = n / 2; i < n; i++) {
        int range = 0;
        while (i + range < n && i - 1 - range >= 0 && s[i + range] == s[i - 1 - range]) {
            range++;
        }
        if (i + range == n) {
            string tmp = s.substr(0, n - 2 * range);
            reverse(tmp.begin(), tmp.end());
            res1 = s + tmp;
            break;
        }
    }
    for (int i = n / 2; i < n; i++) {
        if (i == n - 1) {
            string tmp = s.substr(0, n - 1);
            reverse(tmp.begin(), tmp.end());
            res2 = s + tmp;
            break;
        }
        
        int range = 0;
        while (i + range < n && s[i + range] == s[i - range]) {
            range++;
        }
        if (i + range == n) {
            string tmp = s.substr(0, n - 1 - 2 * range);
            reverse(tmp.begin(), tmp.end());
            res2 = s + tmp;
            break;
        }
    }

    if (res1.size() == 0) {
        cout << res2;
        return 0;
    }
    
    if (res1.size() <= res2.size()) {
        cout << res1;
    } else {
        cout << res2;
    }
    
    
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。