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

2つの文字列 text1 と text2 が与えられたとき、それらの最長共通部分列（Longest Common Subsequence：LCS）の長さを求めることを考えます。

まず用語を整理しましょう。文字列の部分列（subsequence）とは、元の文字列からいくつかの文字を削除して作られる新しい文字列のことであり、残った文字の相対的な順序は変わりません。例えば「abe」は「abcde」の部分列ですが、「adc」は順序が崩れるため部分列ではありません。

そして共通部分列とは、2つの文字列のどちらにも現れる部分列のことです。共通部分列が存在しない場合は 0 を返します。例えば入力が「abcde」と「ace」であれば、最長の共通部分列は「ace」なので、結果は 3 となります。

解法のアプローチ：動的計画法（DP）

この問題は動的計画法を使うことで効率的に解けます。手順は以下の通りです。

• n を s の長さ、m を x の長さとする
• n または m のどちらかが 0 なら、0 を返す
• s の先頭に空の1文字（スペース）を連結し、インデックスを1始まりにする
• x も同様に先頭に空の1文字を連結する
• (n + 1) × (m + 1) のサイズの二次元配列 dp を定義する
• i を 1 から n まで繰り返す
  • j を 1 から m まで繰り返す
    • dp[i][j] を dp[i][j-1] と dp[i-1][j] の最大値に設定する
    • s[i] == x[j] の場合、dp[i][j] を dp[i][j] と 1 + dp[i-1][j-1] の最大値に更新する
• dp[n][m] を返す

dp[i][j] は「s の先頭 i 文字と x の先頭 j 文字における最長共通部分列の長さ」を表します。文字が一致した場合は左上の値に1を加え、一致しない場合は上または左の大きい方を引き継ぐ、という漸化式がポイントです。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int longestCommonSubsequence(string s, string x) {
        int n = s.size();
        int m = x.size();
        if(!n || !m) return 0;
        s = " " + s;
        x = " " + x;
        int ret = 0;
        vector < vector <int> > dp(n + 1, vector <int>(m + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m ; j++){
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if(s[i] == x[j]) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
};
main(){
    Solution ob;
    cout << (ob.longestCommonSubsequence("abcde", "ace"));
}

入力

"abcde"
"ace"

出力

3

計算量について

このアルゴリズムの時間計算量は O(n × m)、空間計算量も O(n × m) です。dp テーブル全体を保持する代わりに、直前の行だけを保持するように工夫すれば、空間計算量を O(min(n, m)) まで削減することも可能です。