与えられた文字列Aを部分列として含む回文文字列BをC++で見つける方法

問題の概要

文字列Aが与えられたとき、Aを部分列として含む回文文字列Bを見つけることを考えます。ここで部分列とは、元の文字列から一部の文字を削除しても、残りの文字の相対的な順序を変えずに作られる文字列のことです。例えば、文字列「cotst」に対して生成される文字列は「contest」です。また、入力としてA = "ab" を選んだ場合、生成される文字列は「abba」となり、これは回文になっています。

解決のアプローチ

この問題の解法は非常にシンプルです。文字列Aを反転し、その反転した文字列をAの後ろに連結してBを構成します。つまり、次の式で表されます。

B = A + reverse(A)

この方法が常に正しく機能する理由は以下の通りです。

• 必ず回文になる: Bを前から読むと「A + reverse(A)」、後ろから読むと「reverse(reverse(A)) + reverse(A)」、つまり「A + reverse(A)」となり、どちらから読んでも同じ文字列になります。
• Aが部分列になる: BはAで始まるため、Aのすべての文字がBの中に元の順序のまま現れます。

C++での実装例

#include <iostream>
#include <algorithm>
using namespace std;

// 回文かどうかを判定する関数
bool isPalindrome(string str) {
    string temp = str;
    reverse(str.begin(), str.end());
    return str == temp;
}

// 文字列Aから回文文字列Bを生成する関数
string formPalindromeStr(string A) {
    string reversed = A;
    reverse(reversed.begin(), reversed.end());
    string B = reversed + A; // B = reverse(A) + A
    return B;
}

int main() {
    string A = "Hello";
    cout << "The B is: " << formPalindromeStr(A) << endl;
    return 0;
}

出力結果

The B is: olleHHello

コードの解説

このプログラムの動作を順に見ていきましょう。

1. isPalindrome関数: 引数として受け取った文字列を反転し、元の文字列と比較することで、回文かどうかを判定します。
2. formPalindromeStr関数: 入力文字列Aのコピーを作って反転させ、元の文字列と連結することで回文Bを生成します。例えば「Hello」の場合、「olleH」+「Hello」=「olleHHello」となります。
3. main関数: 文字列「Hello」を入力として関数を呼び出し、結果を標準出力に表示します。

このように、文字列を反転して連結するだけで、任意の文字列Aを部分列として含む回文を簡単に生成できることがわかります。