C++で、ある文字列の部分列のうち別の文字列の部分文字列となる最長のものの長さを求める

問題の概要

2つの文字列XとYが与えられたとき、Xの部分列のうち、Yの部分文字列（連続する一部分）として現れるものの中で最も長いものの長さを求めます。

例えば、X = "ABCD"、Y = "BACDBDCD" の場合、出力は 3 になります。これは「ACD」がXの部分列であり、同時にYの部分文字列でもある最長の文字列だからです。

動的計画法によるアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。Xの長さをn、Yの長さをmとすると、(m+1)×(n+1) のサイズのDPテーブルを作成します。

DP[i][j] は「X[0…j] の部分列のうち、Y[0…i] の部分文字列となっているものの最大長」を表します。各セルの値は次の手順で更新していきます。

• i を 1 から m まで繰り返す
  • j を 1 から n まで繰り返す
    • X[j-1] と Y[i-1] が一致する場合：DP[i][j] = 1 + DP[i-1][j-1]
    • それ以外の場合：DP[i][j] = DP[i][j-1]

文字が一致したときは左上のセルに1を加えて部分列を延長し、一致しないときは左隣のセルの値を引き継ぐ、というシンプルな漸化式になっています。

最終的な答えは、max(DP[i][n])（1 ≤ i ≤ m）です。これは「Yのどこかの位置で部分文字列として完結している、Xの最長部分列の長さ」に相当します。

C++での実装例

#include<iostream>
#define MAX 100
using namespace std;
int maxSubLength(string x, string y) {
   int table[MAX][MAX];
   int n = x.length();
   int m = y.length();
   // テーブルを0で初期化
   for (int i = 0; i <= m; i++)
      for (int j = 0; j <= n; j++)
   table[i][j] = 0;
   // 動的計画法による更新
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (x[j - 1] == y[i - 1])
            table[i][j] = 1 + table[i - 1][j - 1];
         else
            table[i][j] = table[i][j - 1];
      }
   }
   // 各行の最終列から最大値を取得
   int ans = 0;
   for (int i = 1; i <= m; i++)
   ans = max(ans, table[i][n]);
   return ans;
}
int main() {
   string x = "ABCD";
   string y = "BACDBDCD";
   cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
}

実行結果

Length of Maximum subsequence substring is: 3

計算量について

このアルゴリズムの時間計算量はO(m×n)、空間計算量もO(m×n)です。2つの文字列のすべての文字ペアを一度ずつ比較すればよいため、総当たり的に部分列を列挙する方法（指数時間）と比べて大幅に効率的です。なお、各行の更新は直前の行しか参照しないため、工夫次第で使用メモリをO(n)まで削減することも可能です。