C++で最長共通部分列（LCS）を求める方法：動的計画法による解説

2つの文字列 text1 と text2 が与えられたとき、それらの最長共通部分列（Longest Common Subsequence：LCS）の長さを返す問題を考えてみましょう。

部分列と共通部分列とは

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

共通部分列とは、2つの文字列に共通して現れる部分列のことです。共通部分列が存在しない場合は 0 を返します。

例として、入力が「abcde」と「ace」の場合、共通部分列は「ace」なので、結果は 3 となります。

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

この問題は動的計画法を用いて効率的に解けます。以下の手順で進めます。

1. n を s の長さ、m を x の長さとする
2. n または m が 0 の場合は 0 を返す
3. s と x の先頭に空白文字を追加し、インデックスを 1 から扱えるようにする
4. (n + 1) × (m + 1) のサイズの二次元配列 dp を定義する
5. i を 1 から n まで、j を 1 まで m までループさせる
   • dp[i][j] = max(dp[i][j-1], dp[i-1][j]) とする
   • s[i] == x[j] の場合、dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]) と更新する
6. dp[n][m] を答えとして返す

このDPテーブルでは、dp[i][j] が「s の先頭 i 文字と x の先頭 j 文字における最長共通部分列の長さ」を表します。文字が一致したときは左上の値に1を加え、一致しないときは上または左の大きい方を引き継ぐことで、LCSの長さを段階的に構築していきます。

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) です。2つの文字列の長さがそれぞれ n と m の場合、すべてのセルを一度ずつ埋めるだけでよいため、総当たり的に全ての部分列を調べる指数時間のアプローチと比べて大幅に高速です。

さらにメモリを節約したい場合、各行の更新には直前の行しか必要ないため、ローリング配列を使って O(min(n, m)) の空間計算量まで削減することも可能です。

まとめ

• LCSは動的計画法を使えば O(n × m) で効率的に求められる
• dp[i][j] は「s の i 文字目まで」と「x の j 文字目まで」のLCS長を表す
• 文字一致時は dp[i-1][j-1] + 1、不一致時は dp[i-1][j] と dp[i][j-1] の最大値を採用する