最長共通部分列（LCS）を求めるJavaプログラムの解説

最長共通部分列（Longest Common Subsequence：LCS）とは、2つの文字列に共通して現れる部分列の中で最も長いものを指します。本記事では、動的計画法を用いてLCSの長さを効率的に求める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

プログラムの仕組み

subseqメソッドの処理内容

Demoクラス内に定義された「subseq」メソッドは、引数として渡された2つの文字配列に対する最長共通部分列の長さを返します。

まず、my_arr[1つ目の文字列の長さ+1][2つ目の文字列の長さ+1]というサイズの二次元配列を作成します。続いて、2つのforループを使って両方の文字列の長さ分だけ繰り返し処理を行います。

• インデックス i または j のどちらかが0の場合、そのセルには0を代入します（空の文字列との比較では共通部分列が存在しないため）。
• 文字 a[i-1] と b[j-1] が一致する場合は、左上のセルの値に1を加えた値を格納します。
• 一致しない場合は、上のセルと左のセルのうち大きい方の値を採用します。

mainメソッドの処理内容

mainメソッドでは、Demoクラスの新しいインスタンスを生成し、2つの文字列「MNSQR」と「PSQR」を定義しています。それぞれの文字列は toCharArray() メソッドによってchar型の配列に変換され、その長さも別々の変数に格納されます。最後に、これらの値を引数としてsubseqメソッドを呼び出し、結果を出力します。

動的計画法による効率化

このプログラムで採用されているのは動的計画法（Dynamic Programming）という手法です。一度計算した値を二次元配列に保存しておくことで、再帰処理のように同じ値を何度も再計算する無駄を省いています。過去に計算済みの要素が必要になった際は、配列から即座に値を取り出せるため、計算量を大幅に削減できます。

この例では、文字列「MNSQR」と「PSQR」の共通部分列は「SQR」であるため、出力結果として長さ「3」が表示されます。