C++で最長回文部分列の長さを求めるアルゴリズム

文字列 s が与えられたとき、その中に含まれる最長の回文部分列（パリンドローム・サブシーケンス）の長さを求める問題を考えます。文字列の最大長は 1000 と仮定できます。たとえば入力が "bbbab" の場合、出力は 4 になります。このとき "bbbb" が回文部分列の一例です。

解法のアプローチ

この問題は、「元の文字列 s と、それを逆順にした文字列 x の最長共通部分列（LCS）の長さを求める」ことで解決できます。回文は前後どちらから読んでも同じになるため、元の文字列と逆順の文字列の両方に共通して現れる最長の部分列こそが、最長回文部分列となるからです。

アルゴリズムの手順

• x := s として x を逆順にし、n := s のサイズとする
• n が 0 の場合は 0 を返す
• s と x の先頭にそれぞれ空白を 1 つ追加する（インデックスを 1 始まりに揃えるため）
• (n + 1) × (n + 1) のサイズの DP テーブル dp を作成する
• i を 1 から n まで、j を 1 から n まで繰り返す：
  • dp[i][j] := max(dp[i][j − 1], dp[i − 1][j])
  • x[i] == s[j] の場合、dp[i][j] := max(dp[i][j], 1 + dp[i − 1][j − 1])
• dp[n][n] を返す

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestPalindromeSubseq(string s) {
      string x = s;
      reverse(x.begin(), x.end());
      int n = s.size();
      if(!n) return 0;
      s = " " + s;
      x = " " + x;
      int ret = 0;
      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][j - 1], dp[i - 1][j]);
            if(x[i] == s[j]) {
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
         }
      }
      return dp[n][n];
   }
};
main(){
   Solution ob;
   cout << (ob.longestPalindromeSubseq("bbbab"));
}

入力

"bbbab"

出力

4

計算量について

このアルゴリズムでは、DP テーブルの全マスを一度ずつ埋めていくため、時間計算量は O(n²)、空間計算量も同様に O(n²) となります。文字列の最大長が 1000 であっても、十分に現実的な時間で処理できる設計です。