アルゴリズム入門講座: 11月 2019

最長共通部分列問題の例題とその解法アルゴリズムについてまとめます。

最長共通部分列問題の例題

最長共通部分列

最長共通部分列問題 (Longest Common Subsequence problem: LCS)は、
２つの与えられた列 X={x1,x2,...,xm}と Y={y1,y2,...,yn}の最長共通部分列を求める問題です。

ある列 Zが X と Y 両方の部分列であるとき、Z を X とY の共通部分列と言います。
例えば、X={a,b,c,b,d,a,b}, Y={b,d,c,a,b,a} とすると、列 {b,c,a} は X と Y の共通部分列です。
一方、列 {b,c,a} は X と Y の最長共通部分列ではありません。

なぜなら、その長さは 3 であり、長さ 4 の共通部分列 {b,c,b,a} が存在するからです。
長さが 5 以上の共通部分列が存在しないので、列 {b,c,b,a} は X と Yの最長共通部分列の１つです。

与えられた２つの文字列 X、Yに対して、最長共通部分列 Zの長さを出力するプログラムを作成してください。
与えられる文字列は英文字のみで構成されています。

入力

複数のデータセットが与えられます。最初の行にデータセットの数 q が与えられます。続く 2×q 行にデータセットが与えられます。
各データセットでは２つの文字列 X, Yがそれぞれ１行に与えられます。

出力

各データセットについて X, Y の最長共通部分列 Zの長さを１行に出力してください。

制約

1 ≤ q ≤ 150

1 ≤ X,Yの長さ ≤ 1,000

Xまたは Y の長さが 100 を超えるデータセットが含まれる場合、qは 20 以下である。

入力例1

3
abcbdab
bdcaba
abc
abc
abc
bc

出力例1

4
3
2

最長共通部分列(LSC)問題の考え方

2つの文字列$\{x_1,x_2...,x_i\}$を$X_i$、$\{y_1,y_2...,y_j\}$を$Y_j$と表すことにします。
サイズがそれぞれm,nの2つの列X,YのLSCは$X_m$と$Y_n$のLCSを求めることで得られます。
これを部分問題に分割して考えます。

$X_mとY_n$のLCSを求める時は、以下の2つの場合を考えます。

$X_m = y_n$の場合

$X_m = y_n$の場合は、$X_{m - 1}$と$Y_{n - 1}$のLCSに$x_m(= y_n)$を連結したものが$X_m$と
$Y_n$のLCSとなります。

例えば、$X = \{a,b,c,c,d,a\},Y = \{a,b,c,b,a\}$のとき$x_m = y_n$なので、
$X_{m - 1}$と$Y_{n - 1}$のLCSである{a,b,c}に$X_m(= a)$を連結したものが$X_m$と$Y_n$のLCSとなる。

$x_m \neq y_n$の場合

$x_m \neq y_n$の場合は、$X_{m - 1}$と$Y_n$のLCSあるいは$X_m$と$Y_{n - 1}$のLCSのどちらか長いほうが、 $X_m$と$Y_n$のLCSになります。

例えば、$X = \{a,b,c,c,d,b\},Y = \{a,b,c,b,a\}$のとき$X_{m - 1}$と$Y_n$のLCSは${a,b,c}$、
$X_m$と$Y_{n - 1}$のLCSは$\{a,b,c,b\}$なので、$X_m$と$Y_{n - 1}$のLCSが$X_m$と$Y_n$のLCSになります。

最長共通部分列(LSC)解法アルゴリズム

次のような変数を用意して、LCSの部分問題の解を求めていきます

c[m + 1][n + 1]

c[i][j]を$X_i$と$Y_j$のLCSの長さとする2次元配列

$c[i][j]$の値は以下のケースの漸化式で求めることができます。

$c[i][j] = 0$ {if i == 0 or j == 0}

$c[i][j] = c[i - 1][j - 1] + 1 $ {if i,j > 0 and $x_i = y_j$}

$c[i][j] = max(c[i][j - 1],c[i - 1][j])$ {if i,j > 0 and $x_i \neq y_j$}

最長共通部分列(LSC)解法疑似アルゴリズム

これらに基づいて、2つの列XとYのLCSを動的計画法で求める疑似アルゴリズムは以下のようになります

lsc(X,Y)
 m = X.length
 n = Y.length

 for i = 1 to m
   c[i][0] = 0
 for j = 1 to n
   c[0][j] = 0
 for i = 1 to m
   for j = 1 to n
     if X[i] == Y[j]
       c[i][j] = c[i - 1][j - 1] + 1
     else if c[i - 1][j] >= c[i][j - 1]
       c[i][j] = c[i - 1][j]
     else
       c[i][j] = c[i][j - 1]

最長共通部分列(LSC)アルゴリズムの計算量

nとmの２重ループより、$O(mn)$のアルゴリズムになります。

最長共通部分列問題のc++による回答

最後に例題の回答を書きます。


#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

#define N 1000

int lcs(string x,string y){
    int c[N + 1][N + 1] = {};
    int maxl = 0;
    x = ' ' + x; // X[0]に空白を挿入
    y = ' ' + y; // Y[0]に空白を挿入

    for(int i = 1;i <= x.size();++i){
        for(int j = 1;j <= y.size();++j){
            if(x[i] == y[j]){
                c[i][j] = c[i - 1][j - 1] + 1;
            }else{
                c[i][j] = max(c[i - 1][j],c[i][j - 1]);
            }
            maxl = max(maxl,c[i][j]);
        }
    }
    
    for(int i = 1;i <= x.size();++i){
        for(int j = 1;j <= y.size();++j){
            if(x[i] == y[j]){
                c[i][j] = c[i - 1][j - 1] + 1;
            }else{
                c[i][j] = max(c[i - 1][j],c[i][j - 1]);
            }
            maxl = max(maxl,c[i][j]);
        }
    }
    // 空白一致分
    return maxl - 1;
}

int main(){
    string s1,s2;
    int n;
    cin >> n;
    
    for(int i = 0;i < n;++i){
        cin >> s1 >> s2;
        cout << lcs(s1,s2) << endl;
    }
}

アルゴリズム入門講座

2019年11月2日土曜日

最長共通部分列問題とその解法アルゴリズムとc++のコード