最長共通部分列のためのJavaプログラム

以下は最長共通部分列のJavaプログラムです-

例

public class Demo{
   int subseq(char[] a, char[] b, int a_len, int b_len){
      int my_arr[][] = new int[a_len + 1][b_len + 1];
      for (int i = 0; i <= a_len; i++){
         for (int j = 0; j <= b_len; j++){
            if (i == 0 || j == 0)
            my_arr[i][j] = 0;
            else if (a[i - 1] == b[j - 1])
            my_arr[i][j] = my_arr[i - 1][j - 1] + 1;
            else
            my_arr[i][j] = max_val(my_arr[i - 1][j], my_arr[i][j - 1]);
         }
      }
      return my_arr[a_len][b_len];
   }
   int max_val(int val_1, int val_2){
      return (val_1 > val_2) ? val_1 : val_2;
   }
   public static void main(String[] args){
      Demo my_inst = new Demo();
      String my_str_1 = "MNSQR";
      String my_str_2 = "PSQR";
      char[] a = my_str_1.toCharArray();
      char[] b = my_str_2.toCharArray();
      int a_len = a.length;
      int b_len = b.length;
      System.out.println("The length of the longest common subsequence is"+ " " + my_inst.subseq(a, b, a_len,       b_len));
   }
}

出力

The length of the longest common subsequence is 3

Demoという名前のクラスには、指定された文字列の最長共通部分列を返す「subseq」という関数が含まれています。つまり、str_1 [0 to len（str_1-1）、str_2（0 to len（str_2-1）// 2'for' loopsは両方の文字列の長さにわたって繰り返され、「i」と「j」の両方が0の場合、配列の特定のインデックスは0に割り当てられます。それ以外の場合、my_arr[最初の文字列の長さ+1][2番目の文字列の長さ+ 1]が構築されます。

main関数は、Demoクラスの新しいインスタンスを定義し、my_str_1とmy_str_2の2つの文字列を定義します。両方の文字列は配列に変換され、それらの長さは別々の変数に格納されます。これらの値に対して関数が呼び出されます。

これは動的計画法であり、1つの値が計算されて配列に格納されるため、再帰のように何度も計算する必要がなくなります。以前に計算された要素が必要な場合は常に、配列からフェッチされます。