最長共通部分列（LCS）とは？動的計画法による解法をC++サンプル付きで解説

最長共通部分列（LCS）とは

最長共通部分列（Longest Common Subsequence：LCS）とは、与えられた2つの文字列や配列のどちらにも共通して現れる部分列の中で、最も長いものを指します。

この問題を単純な全探索で解こうとすると、同じ部分問題が何度も繰り返し計算されてしまいます。そこで役立つのが、動的計画法（Dynamic Programming）の「部分問題の重複（Overlapping Substructure）」という性質です。一度計算した部分問題の結果を表（テーブル）に保存しておけば、あとは以前の結果を参照しながら次の結果を順に求めていくだけでよく、計算の手間を大幅に削減できます。

入力と出力

入力：
異なる文字や記号を含む2つの文字列。
文字列1：AGGTAB
文字列2：GXTXAYB

出力：
最長共通部分列の長さ。この例では 4。
AGGTAB と GXTXAYB において、下線部の文字（G・T・A・B）が両方の文字列に共通し、かつ元の順序どおりに現れています。

アルゴリズム

longestComSubSeq(str1, str2)

入力 − 最長共通部分列の長さを求める対象となる2つの文字列。

出力 − LCS の長さ。

Begin
    m := str1 の長さ
    n := str2 の長さ
    (m+1) × (n+1) のサイズで longSubSeq 表を定義する

    for i := 0 to m, do
        for j := 0 to n, do
            if i = 0 or j = 0, then
                longSubSeq[i,j] := 0
            else if str1[i-1] = str2[j-1], then
                longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
            else
                longSubSeq[i,j] := longSubSeq[i-1, j] と
                longSubSeq[i, j-1] の最大値
        done
    done

    longSubSeq[m, n]
End

C++での実装例

#include<iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a : b;
}

int longestComSs( string str1, string str2) {
    int m = str1.size();
    int n = str2.size();
    
    int longSubSeq[m+1][n+1];
    
    //longSubSeq[i][j] には、str1 の 0〜i-1 文字目と str2 の 0〜j-1 文字目の LCS が格納される
    for (int i=0; i<=m; i++) {
        for (int j=0; j<=n; j++) {
            if (i == 0 || j == 0)
                longSubSeq[i][j] = 0;
            else if (str1[i-1] == str2[j-1])
                longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
            else
                longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
        }
    }
    return longSubSeq[m][n];
}

int main() {
    string str1 = "AGGTAB";
    string str2 = "GXTXAYB";

    cout << "Length of Longest Common Subsequence is: " << longestComSs( str1, str2);
}

実行結果

Length of Longest Common Subsequence is: 4

計算量

この動的計画法による解法では、(m+1)×(n+1) の表をすべて埋めるため、時間計算量は O(m×n)、必要なメモリ（空間計算量）も同様に O(m×n) となります。指数時間がかかる全探索的なアプローチと比べて、非常に効率的であることがわかります。