競技プログラミング 知識集積所

最長共通部分列

概要

$2$ つの数列または文字列に共通する部分列を作るとき、その長さを最大化する問題。
動的計画法を用いて解ける。

ABCでは主にE問題以降で登場する。

典型問題例

コード例

最長共通部分列を求める通常の方法

例えば、次の $2$ つの数列があったとする。

A = {1, 2, 3, 4, 5}
B = {1, 4, 3, 5, 2}

この場合、

C = {1, 4, 5}

という数列は、$A$ からも $B$ からも一部の要素を元の順序を保って選ぶことで作られる。
このような $C$ を、$A$ と $B$ の共通部分列という。
共通部分列の中で最も長いものを、最長共通部分列という。

最長共通部分列は、二次元の動的計画法を用いて求められる。
次のようなDPテーブルを用意する。

dp[i][j] = A の先頭 i 個と B の先頭 j 個の最長共通部分列の長さ

片方の要素数が $0$ 個なら、共通部分列の長さも $0$ である。
そのため、初期値は次のようになる。

$$
dp[0][j]=0,\qquad dp[i][0]=0
$$

A[i] と B[j] が等しい場合、その値を共通部分列の末尾に追加できる。
異なる場合は、どちらか一方を使わない場合の大きい方を採用する。
したがって、遷移は次のようになる。

$$
dp[i+1][j+1]
=
\begin{cases}
dp[i][j]+1 & (A[i]=B[j]) \\
\max(dp[i][j+1],\ dp[i+1][j]) & (A[i]\neq B[j])
\end{cases}
$$

これに従ってDPテーブルを埋めると、次のようになる。

$B\backslash A$ ― $1$ $2$ $3$ $4$ $5$
― $0$ $0$ $0$ $0$ $0$ $0$
$1$ $0$ $1$ $1$ $1$ $1$ $1$
$4$ $0$ $1$ $1$ $1$ $2$ $2$
$3$ $0$ $1$ $1$ $2$ $2$ $2$
$5$ $0$ $1$ $1$ $2$ $2$ $3$
$2$ $0$ $1$ $2$ $2$ $2$ $3$

右下の dp[5][5] から、最長共通部分列の長さは $3$ とわかる。

実際の最長共通部分列を復元する場合は、DPテーブルの右下からバックトレースする。
現在見ている要素が A[i-1] と B[j-1] のとき、次のように移動する。

これを $i=0$ または $j=0$ になるまで繰り返すと、最長共通部分列が後ろから順に得られる。
最後に反転すればよい。

この例では、

{1, 4, 5}

を復元できる。
途中で同じ値のマスから別の方向へ進むと、

{1, 3, 5}

を復元する場合もある。
最長共通部分列は $1$ つとは限らないが、どれか $1$ つを求めればよい問題では、どちらも正解である。

C++での実装例は、次のようになる。

vector<int> lcs(const vector<int>& s, const vector<int>& t) {
  int m = ssize(s);
  int n = ssize(t);
  vector<int> result;
  vector<vector<int>> dp(m+1,vector<int>(n+1,0));
  for (int i=1; i<=m; i++) {
    for (int j=1; j<=n; j++) {
      if (s[i-1]==t[j-1]) {
        dp[i][j] = dp[i-1][j-1]+1;
      } else {
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
      }
    }
  }
  int i = m;
  int j = n;
  while (i>0&&j>0) {
    if (s[i-1]==t[j-1]) {
      i--;
      j--;
      result.emplace_back(s[i]);
    } else if (dp[i-1][j]==dp[i][j]) {
      i--;
    } else if (dp[i][j-1]==dp[i][j]) {
      j--;
    }
  }
  reverse(result.begin(),result.end());
  return result;
}

DPテーブルには $(N+1)(M+1)$ 個の状態があり、各状態を $O(1)$ で更新する。
復元のための移動回数は最大で $N+M$ 回である。

最長増加部分列へ帰着する方法

最長共通部分列を、最長増加部分列のアルゴリズムへ帰着して求める方法もある。

例えば、次の $2$ つの数列の最長共通部分列を考える。

A = {1, 3, 3, 2, 1}
B = {1, 2, 3, 1, 2}

$B$ の各要素について、同じ値が $A$ の何番目にあるかを後ろから列挙する。
（後ろからなのは、$B$ の同じ $1$ 要素に対して、$A$ の複数の位置を同時に選んでしまうことを防ぐため）

B[0]=1 に対応する位置を追加すると、次のようになる。

vec = {4, 0}

B[1]=2 に対応する位置を追加する。

vec = {4, 0, 3}

B[2]=3 に対応する位置を追加する。

vec = {4, 0, 3, 2, 1}

同様に、残りの要素についても追加する。

vec = {4, 0, 3, 2, 1, 4, 0, 3}

この vec の最長増加部分列を求めると、例えば次の列が得られる。

{0, 1, 3}

これは $A$ から選ぶ位置を表す。
対応する値を $A$ から取り出すと、

{1, 3, 2}

となり、$A$ と $B$ の最長共通部分列が得られる。

C++での実装例は、次のようになる。
lis は、最長増加部分列のページで紹介した関数とする。

vector<int> lcs(const vector<int>& s, const vector<int>& t) {
  int m = ssize(s);
  int n = ssize(t);
  map<int,vector<int>> mp;
  for (int i=m-1; i>=0; i--) mp[s[i]].emplace_back(i);
  vector<int> vec;
  for (int j=0; j<n; j++) for (int i : mp[t[j]]) vec.emplace_back(i);
  vector<int> vec2 = lis(vec);
  vector<int> result(vec2.size());
  for (int i=0; i<ssize(vec2); i++) result[i] = s[vec2[i]];
  return result;
}

値が広く分布していて、一致する組が少ない場合には、通常の $O(NM)$ の動的計画法より高速である。
特に双方が同じ要素からなる順列の場合は、$O(N\log N)$ で求められる。

一方、全ての要素が同じ場合、vec の要素数は $NM$ 個になる。
この場合、最長増加部分列の計算に $O(NM\log(NM))$ かかるため、通常の動的計画法より遅くなる。

注意点

部分列は連続していなくてもよい

部分列は、元の順序を保って要素を選んだ列であり、選んだ要素が元の数列内で連続している必要はない。
連続する部分だけを選ぶ最長共通部分文字列とは別の問題である。

関連アルゴリズム

動的計画法

少し小さい問題の答えを利用して、より大きい問題を順に解くアルゴリズム。
最長共通部分列では、$2$ つの列の先頭から使う要素数を状態として持つ。

バックトレース

終了状態から逆向きにたどり、具体的な選び方などを復元する方法。
最長共通部分列そのものを復元するために使う。

最長増加部分列

数列の一部を元の順序を保ったまま選び、狭義単調増加する部分列の長さを最大化する問題。
値が一致する位置を並べた数列の最長増加部分列を求めることで、最長共通部分列を求められる。