Javaで最長の回文部分列を求めるプログラムの実装方法

最長の回文部分列（Longest Palindromic Subsequence）とは、元の文字列から一部の文字を抜き出して並べたとき、前から読んでも後ろから読んでも同じになる列のうち、最も長いものを指します。これを求めるためのJavaコードは以下の通りです。

サンプルコード

public class Demo{
   static String longest_seq(String str_1, String str_2){
      int str_1_len = str_1.length();
      int str_2_len = str_2.length();
      char str_1_arr[] = str_1.toCharArray();
      char str_2_arr[] = str_2.toCharArray();
      int L[][] = new int[str_1_len + 1][str_2_len + 1];
      for (int i = 0; i <= str_1_len; i++){
         for (int j = 0; j <= str_2_len; j++){
            if (i == 0 || j == 0){
               L[i][j] = 0;
            }
            else if (str_1_arr[i - 1] == str_2_arr[j - 1]){
               L[i][j] = L[i - 1][j - 1] + 1;
            }
            else{
               L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
            }
         }
      }
      int my_index = L[str_1_len][str_2_len];
      char[] longest_seq = new char[my_index + 1];
      int i = str_1_len, j = str_2_len;
      while (i > 0 && j > 0){
         if (str_1_arr[i - 1] == str_2_arr[j - 1]){
            longest_seq[my_index - 1] = str_1_arr[i - 1];
            i--;
            j--;
            my_index--;
         }
         else if (L[i - 1][j] > L[i][j - 1]){
            i--;
         } else {
            j--;
         }
      }
      String my_result = "";
      for (int x = 0; x < longest_seq.length; x++){
         my_result += longest_seq[x];
      }
      return my_result;
   }
   static String longestPalSubseq(String str){
      String rev_str = str;
      rev_str = reverse_str(rev_str);
      return longest_seq(str, rev_str);
   }
   static String reverse_str(String str){
      String my_result = "";
      char[] trial = str.toCharArray();
      for (int i = trial.length - 1; i >= 0; i--){
         my_result += trial[i];
      }
      return my_result;
   }
   public static void main(String[] args){
      String str = "HelloHelloo";
      System.out.println("Longest palindromic subsequence is ");
      System.out.println(longestPalSubseq(str));
   }
}

実行結果

Longest palindromic subsequence is
llell

コードの解説

longest_seq 関数

Demoという名前のクラス内にある「longest_seq」関数は、2つの文字列と、それぞれに対応する2つのchar型配列を宣言します。この関数では、配列を順番に走査しながら動的計画法（Dynamic Programming）を用いて最長の回文部分列を導き出します。

動的計画法のポイントは、一度計算した値を表Lに格納しておき、再度同じ計算を行わない点です。これにより無駄な再計算が省かれ、処理全体が効率化されます。

longestPalSubseq 関数

「longestPalSubseq」関数は、対象となる文字列を引数として受け取り、その文字列を反転させたものを引数に「longest_seq」関数を呼び出します。これは、元の文字列と反転した文字列との最長共通部分列（LCS）が、最長の回文部分列と一致するという性質を利用したアプローチです。

reverse_str 関数

「reverse_str」関数は、引数として渡された文字列を逆順に並べ替えるための補助関数です。文字列をchar型配列に変換し、末尾から先頭へ向かって連結することで反転を実現しています。

main 関数

main関数では、対象となる文字列「HelloHelloo」が定義され、「longestPalSubseq」関数が呼び出されます。その結果がコンソールに出力され、この例では「llell」という最長の回文部分列が得られます。

計算量について

このアルゴリズムの時間計算量および空間計算量は、いずれもO(n²)です。文字列の長さが大きくなっても、動的計画法によって各部分問題を一度だけ解くため、全探索に比べて大幅に高速に動作します。