目標

最長共通部分列を実装する

最長共通部分列

２つの列X、Yがあるとします。XとYの共通部分列のうち、最長のものを最長共通部分列（Longest Common Subsequence, LCS）と言います。列は数列など色々なものが考えられますが、ここでは文字列を取り上げます。X = {a, b, c, d}、Y = {a, c, d, e} のとき、最長共通部分列は {a, c, d}となります。ここで注意しておきたいのが、部分列は連続である必要はなく、元の列の要素はとびとびになっていても良いということです。

最長共通部分列問題では、与えられた２つの列の最長共通部分列の長さを求めます。

アルゴリズム

$X = \{x_1, x_2, \dots , x_m\}, Y = \{y_1, y_2, \dots , y_n \}$ に対して、部分列 $X_i = \{x_1, x_2, \dots , x_i \}, Y_j = \{y_1, y_2, \dots , y_j \}$ を考えます。 $X_i, Y_j$ のLCS（LCS(i, j)と書くことにします）は、それまでに計算した値を使って求めることができます。次の２つに場合分けをします。

$x_i = y_j$ の場合： LCS(i-1, j-1)に $x_i = y_j$ を加えたものが LCS(i, j) となります。
$x_i \neq y_j$ の場合： LCS(i, j-1)とLCS(i-1, j)のうち、より長いほうが LCS(i, j) です。

従って、次の漸化式が成り立ちます。

$| LCS(i, j) | = \left \{ \begin{array}{} 0 && (i = 0 \; or \; j = 0) \\ | LCS(i-1, j-1) | + 1 && (i, j > 0 \; and \; x_i = y_j) \\ max( | LCS(i, j-1) | , | LCS(i-1, j) | ) && (i, j > 0 \; and \; x_i \neq y_j) \\ \end{array} \right.$

計算量は $O(nm)$ となります。LCS(m, n)がX、Yの最長共通部分列です。

実装

次の問題を解いてみます。

最長共通部分列 | アルゴリズムとデータ構造 | Aizu Online Judge

解答例：

#include<iostream>
#include<string>
using namespace std;

#define N 1000

int lcs(string x, string y) {
  int i, j, m, n, lcs[N+1][N+1];
  
  m = x.length();
  n = y.length();
  // indexずれを補正
  x = ' ' + x;
  y = ' ' + y;
  
  // 初期値
  for (i = 0; i < m + 1; i++) lcs[i][0] = 0;
  for (j = 0; j < n + 1; j++) lcs[0][j] = 0;
  // 漸化式
  for (i = 1; i <= m; i++) {
    for (j = 1; j <= n; j++) {
      if (x[i] == y[j]) lcs[i][j] = lcs[i-1][j-1] + 1;
      else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
    }
  }

  return lcs[m][n];
}

int main() {
  int i, q, lcs_arr[N];
  string x, y;

  cin >> q;

  for (i = 0; i < q; i++) {
    cin >> x;
    cin >> y;
    lcs_arr[i] = lcs(x, y);
  }    

  for (i = 0; i < q; i++) cout << lcs_arr[i] << endl;
    
  return 0;
}