C++で文字列を回文にするために必要な最小の追加文字数を求める方法

問題文

文字列が与えられたとき、その文字列を回文にするために末尾へ追加する必要のある最小の文字数を求めます。

例

たとえば文字列が「abcac」の場合、2文字を追加して「abcacba」とすれば回文になります。

アルゴリズム

• 文字列がすでに回文であるかどうかを確認します。回文であれば、文字を追加する必要はありません。
• 文字列の先頭から1文字ずつ削除し、残りの文字列が回文になっているかどうかを確認します。
• 文字列が回文になるまで、上記の処理を繰り返します。
• それまでに削除した文字数を、最終的な答えとして返します。

このアプローチのポイントは、「先頭から削除した文字数」がそのまま「末尾に追加すべき文字数」に対応するという点です。先頭の文字を取り除いて残りが回文になれば、取り除いた文字を逆順に末尾へ付け足すことで必ず回文が完成します。

サンプルコード

#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(char *str) {
   int n = strlen(str);
   if (n == 1) {
      return true;
   }
   int start = 0, end = n - 1;
   while (start < end) {
      if (str[start] != str[end]) {
         return false;
      }
      ++start;
      --end;
   }
   return true;
}
int requiredAppends(char *str) {
   if (isPalindrome(str)) {
      return 0;
   }
   return 1 + requiredAppends(str + 1);
}
int main() {
   char *str = "abcac";
   cout << "Characters to be appended = " << requiredAppends(str) << endl;
   return 0;
}

コードの解説

isPalindrome 関数は、文字列の先頭と末尾から順に文字を比較していくことで、その文字列が回文かどうかを判定します。両端のポインタ start と end を中央に向かって移動させ、不一致が1つでも見つかれば false を返します。

requiredAppends 関数は再帰的に呼び出されます。まず現在の文字列が回文かどうかを判定し、回文でなければ先頭の1文字をスキップした残りの文字列に対して自分自身を呼び出します。回文が見つかった時点で、それまでにスキップした文字数の合計（＝末尾に追加すべき文字数）が確定します。

計算量は、最悪の場合に回文判定を文字数の回数だけ繰り返すため O(n²) となります。文字列が短い場合には十分実用的なシンプルな実装です。

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Characters to be appended = 2