最長共通部分列（LCS）を求めるC++プログラム

部分列とは、元の文字列から要素を取り出す際に、元の順序を保ったまま作られる列のことです。例えば、文字列「stuv」の部分列には「stu」「tuv」「suv」などがあります。

長さnの文字列から作成できる部分列の数は、2ⁿ通り存在します。そのため、すべての部分列を総当たりで調べる方法は、文字列が長くなるほど計算量が爆発的に増えてしまいます。

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

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

例えば、文字列「ABCDGH」と「AEDFHR」の場合、最長共通部分列は「ADH」となり、その長さは3です。

再帰を使ったC++プログラム

以下は、再帰呼び出しを用いて最長共通部分列の長さを求めるC++プログラムの例です。末尾の文字が一致した場合は1を加えて再帰的に処理を進め、一致しない場合はどちらか一方の文字列を短くした場合の結果の最大値を取ります。

#include <iostream>
#include <string.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
    if (m == 0 || n == 0)
        return 0;
    if (X[m - 1] == Y[n - 1])
        return 1 + lcs(X, Y, m - 1, n - 1);
    else
        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int max(int a, int b){
    return (a > b) ? a : b;
}
int main(){
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    printf("Length of LCS is %d\n", lcs(X, Y, m, n));
    return 0;
}

実行結果

Length of LCS is 4

このプログラムでは、文字列「AGGTAB」と「GXTXAYB」の最長共通部分列として「GTAB」が見つかり、その長さ4が出力されます。

補足：動的計画法による効率化

上記の再帰的な実装は理解しやすい反面、同じ部分問題を何度も計算するため、最悪の場合時間計算量がO(2ⁿ)となり非効率です。実用的な場面では、メモ化や動的計画法（DP）を用いることで、時間計算量をO(m×n)まで抑えることができます。DP表を用いて各部分問題の解を保存しながら計算することで、より長い文字列に対しても高速にLCSを求められます。