C++で文字列を回文にするための最小挿入回数を求める方法

文字列 s が与えられ、これを回文にすることを考えます。各ステップでは任意の位置に任意の文字を挿入することができ、回文を完成させるために必要な最小の挿入文字数を求めます。

例えば、文字列が「mad」の場合、答えは 2 になります。これは、「mad」の先頭に「da」を追加して「damad」とするか、末尾に「am」を追加して「madam」とすることで回文を作れるためです。

解法のアプローチ：LCS（最長共通部分列）を活用

この問題は最長共通部分列（LCS）を使った動的計画法で効率的に解けます。鍵となるのは、元の文字列とその逆順の文字列との最長共通部分列の長さが、最長回文部分列の長さと一致するという性質です。したがって、必要な最小挿入回数は次の式で表せます。

最小挿入回数 ＝ 文字列の長さ − 最長回文部分列の長さ

アルゴリズムの手順

• 関数 lcs() を定義します。引数として文字列 s を受け取り、x = s とします。
• n を s のサイズとします。
• 文字列 x を反転（リバース）します。
• s と x のそれぞれの先頭に空白文字を連結します（インデックスを1始まりに揃えるため）。
• サイズ (n + 1) × (n + 1) の2次元配列 dp を定義します。
• i を 1 から n まで、j を 1 から n まで二重ループで処理します。
  • dp[i][j] を max(dp[i−1][j], dp[i][j−1]) とします。
  • s[i] と x[j] が一致する場合は、dp[i][j] を max(dp[i][j], dp[i−1][j−1] + 1) で更新します。
• dp[n][n] を返します。
• メイン側では「s のサイズ − lcs(s)」を結果として返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int lcs(string s){
      string x = s;
      int n = s.size();
      reverse(x.begin(), x.end());
      s = " " + s;
      x = " " + x;
      vector < vector <int> > dp(n + 1, vector <int>(n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(s[i] == x[j]){
               dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
         }
      }
      return dp[n][n];
   }
   int minInsertions(string s) {
      return s.size() - lcs(s);
   }
};
main(){
   Solution ob;
   cout << (ob.minInsertions("mad"));
}

入力

“mad”

出力

2

計算量について

このアルゴリズムの計算量は、LCSの計算に二重ループを使用するため時間計算量 O(n²)、DPテーブルを保持するため空間計算量 O(n²) となります。文字列の長さが数千程度であれば十分実用的な速度で動作します。