Chương trình C++ tìm chuỗi sau khi chèn 'a' để không thành palindrome

Cho chuỗi S chỉ chứa chữ cái tiếng Anh thường. Phải chèn đúng một ký tự 'a' vào S. Nếu sau khi chèn chuỗi không phải palindrome, trả về chuỗi đó; ngược lại trả về "impossible".

Ví dụ

Với S = "bpapb", đầu ra là "bpaapb" (chèn 'a' ở giữa).

Giải thuật

Thử chèn 'a' ở cuối: S + 'a'. Nếu không phải palindrome, trả về. Ngược lại thử chèn ở đầu: 'a' + S. Nếu không phải palindrome, trả về. Còn lại trả về "Impossible".

Mã C++

#include <bits/stdc++.h>
using namespace std;

bool p(const string& s) {
    for (int i = 0; i < s.size() / 2; i++)
        if (s[i] != s[s.size() - 1 - i])
            return false;
    return true;
}

string solve(string S) {
    if (!p(S + 'a'))
        return S + 'a';
    else if (!p('a' + S))
        return 'a' + S;
    else
        return "Impossible";
}

int main() {
    string S = "bpapb";
    cout << solve(S) << endl;
}

Đầu vào / Đầu ra

Input: "bpapb"
Output: bpapba