文字列Sを部分列として含む回文文字列を求めるC++プログラム

長さnの文字列Sが与えられたとします。このとき、Tが回文であり、かつSがTの部分列(サブシーケンス)となるような文字列Tを見つける必要があります。

例えば、入力が S = "ab" の場合、出力は "abba" となります(他にも "aabaa" など、複数の正解が存在します)。

解法のアプローチ

この問題は、非常にシンプルな発想で解くことができます。以下の手順に従います。

1. 結果の文字列resをSで初期化します。
2. 文字列Sを反転します。
3. resに反転したSを連結します。
4. resを返します。

つまり、元の文字列とその逆順の文字列を連結するだけで、必ず回文となる文字列を作ることができます。中央を境に左右が対称になるため、結果は常に回文の条件を満たします。また、元の文字列Sが前半にそのまま含まれているため、Sは結果の部分列にもなっています。

実装例

以下のC++コードで実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    string res = S;
    reverse(S.begin(), S.end());
    res += S;
    return res;
}
int main(){
    string S = "ab";
    cout << solve(S) << endl;
}

入力

ab

出力

abba

計算量について

このアルゴリズムの時間計算量はO(n)です。文字列の反転と連結はいずれも線形時間で実行できるため、非常に効率的です。空間計算量も結果の文字列を格納するためにO(n)必要となります。シンプルながら、あらゆる入力文字列に対して確実に回文を生成できる優れたアプローチです。