C++: Tìm chuỗi palindrome chứa S làm subsequence

Bài toán: Cho chuỗi S. Tìm chuỗi T là palindrome và S là subsequence của T.

Giải pháp đơn giản: T = S + reverse(S). Luôn là palindrome và chứa S làm tiền tố (do đó là subsequence).

Code C++

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

string solve(string S) {
    string T = S;
    reverse(S.begin(), S.end());
    T += S;
    return T;
}

int main() {
    cout << solve("ab") << endl; // abba
    return 0;
}

Kết quả

abba

Lưu ý: Đáp án không duy nhất. "aabaa" cũng hợp lệ. Giải pháp này cho độ dài 2|S|.