最長共通部分列 |すべての LCS の検索

2つのシーケンスが与えられた場合、それらに存在する可能性のある最長共通部分列をすべて出力します。

例えば、

Input: X = XMJYAUZ, Y = MZJAWXU
Output: MJAU

Input: X = ABCBDAB, Y = BDCABA
Output: BCAB, BCBA, BDAB

Practice this problem

の中に前の投稿、最長共通部分列の長さを見つける方法について説明しました。この投稿では、最長共通部分列自体を印刷する方法について説明します。

させて X なれ XMJYAUZ と Y なれ MZJAWXU。間の最長共通部分列 X と Y は MJAU。次の表は、プレフィックス間の最長共通部分列の長さを示しています。 X と Y。 The i'th 行と j'th 列はLCSの部分文字列の長さを示します X[0…i-1] と Y[0…j-1].

Longest Common subsequence

強調表示された数字は、LCSを読み取るときに右下から左上隅までたどるパスを示しています。現在の文字が X と Y 等しい(太字で示されている)、それらはLCSの一部であり、斜めに移動します。現在の文字が X と Y 異なる場合は、どちらのセルの数が多いかに応じて、上または左に移動します。これは、LCSを X[0…i-2], Y[0…j-1]、また X[0…i-1], Y[0…j-2].

次のC++、Java、およびPythonの実装は、ルックアップテーブルをボトムアップ方式次に、LCSを再帰的にに検索しますトップダウンルックアップテーブルの値を使用する方法。

C++

#include <iostream>

#include <vector>

#include <string>

using namespace std;

//の最長共通部分列を見つける再帰的関数

//文字列`X[0…m-1]`と`Y[0…n-1]`

string LCS(string X, string Y, int m, int n, auto &lookup)

{

//いずれかのシーケンスの終わりに達した場合、空の文字列を返します

if (m == 0 || n == 0) {

return string("");

}

//`X`と`Y`の最後の文字が一致する場合

if (X[m - 1] == Y[n - 1])

{

//現在の文字(`X[m-1]`または`Y[n-1]`)をのLCSに追加します

//サブストリング`X[0…m-2]`および`Y[0…n-2]`

return LCS(X, Y, m - 1, n - 1, lookup) + X[m - 1];

}

//それ以外の場合、`X`と`Y`の最後の文字が異なる場合

//現在のセルの一番上のセルの値が左よりも大きい場合

//セル、次に文字列 `X`の現在の文字を削除し、LCSを検索します

//部分文字列の`X[0…m-2]`、`Y[0…n-1]`

if (lookup[m - 1][n] > lookup[m][n - 1]) {

return LCS(X, Y, m - 1, n, lookup);

}

else {

//現在のセルの左側のセルの値が上部よりも大きい場合

//セル、次に文字列 `Y`の現在の文字を削除し、LCSを検索します

//部分文字列の`X[0…m-1]`、`Y[0…n-2]`

return LCS(X, Y, m, n - 1, lookup);

}

//LCSの長さを見つけることによってルックアップテーブルを埋める関数

//部分文字列`X[0…m-1]`と`Y[0…n-1]`の

void LCSLength(string X, string Y, int m, int n, auto &lookup)

{

//ルックアップテーブルをボトムアップ方式で入力します

for (int i = 1; i <= m; i++)

{

for (int j = 1; j <= n; j++)

{

//`X`と`Y`の現在の文字が一致する場合

if (X[i - 1] == Y[j - 1]) {

lookup[i][j] = lookup[i - 1][j - 1] + 1;

}

//それ以外の場合、`X`と`Y`の現在の文字が一致しない場合

else {

lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);

}

//文字列`X`と`Y`のすべてのLCSを検索する関数

string LCS(string X, string Y)

{

int m = X.length(), n = Y.length();

// lookup[i][j]は、部分文字列`X[0…i-1]`と`Y[0…j-1]`のLCSの長さを格納します

vector<vector<int>> lookup(m + 1, vector<int>(n + 1));

//ルックアップテーブルを埋めます

LCSLength(X, Y, m, n, lookup);

// return LCS

return LCS(X, Y, m, n, lookup);;

}

int main()

{

string X = "XMJYAUZ", Y = "MZJAWXU";

//最長共通部分列を見つけます

cout << LCS(X, Y);

return 0;

}

ダウンロードコードを実行する

出力:

MJAU

Java

class Main

{

//文字列`X[0…m-1]`の最長共通部分列を見つける関数

//および`Y[0…n-1]`

public static String LCS(String X, String Y, int m, int n, int[][] lookup)

{

//いずれかのシーケンスの終わりに達した場合、空の文字列を返します

if (m == 0 || n == 0) {

return new String();

}

//`X`と`Y`の最後の文字が一致する場合

if (X.charAt(m - 1) == Y.charAt(n - 1))

{

//現在の文字(`X[m-1]`または`Y[n-1]`)をのLCSに追加します

//サブストリング`X[0…m-2]`および`Y[0…n-2]`

return LCS(X, Y, m - 1, n - 1, lookup) + X.charAt(m - 1);

}

//それ以外の場合、`X`と`Y`の最後の文字が異なる場合

//現在のセルの一番上のセルの値が左よりも大きい場合

//セル、次に文字列 `X`の現在の文字を削除し、LCSを検索します

//部分文字列の`X[0…m-2]`、`Y[0…n-1]`

if (lookup[m - 1][n] > lookup[m][n - 1]) {

return LCS(X, Y, m - 1, n, lookup);

}

else {

//現在のセルの左側のセルの値が上部よりも大きい場合

//セル、次に文字列 `Y`の現在の文字を削除し、LCSを検索します

//部分文字列の`X[0…m-1]`、`Y[0…n-2]`

return LCS(X, Y, m, n - 1, lookup);

}

//LCSの長さを見つけることによってルックアップテーブルを埋める関数

//部分文字列`X[0…m-1]`と`Y[0…n-1]`の

public static void LCSLength(String X, String Y, int m, int n, int[][] lookup)

{

//ルックアップテーブルをボトムアップ方式で入力します

for (int i = 1; i <= m; i++)

{

for (int j = 1; j <= n; j++)

{

//`X`と`Y`の現在の文字が一致する場合

if (X.charAt(i - 1) == Y.charAt(j - 1)) {

lookup[i][j] = lookup[i - 1][j - 1] + 1;

}

//それ以外の場合、`X`と`Y`の現在の文字が一致しない場合

else {

lookup[i][j] = Integer.max(lookup[i - 1][j], lookup[i][j - 1]);

}

public static void main(String[] args)

{

String X = "XMJYAUZ", Y = "MZJAWXU";

int m = X.length(), n = Y.length();

// lookup[i][j]は、部分文字列`X[0…i-1]`と`Y[0…j-1]`のLCSの長さを格納します

int[][] lookup = new int[m + 1][n + 1];

//ルックアップテーブルを埋めます

LCSLength(X, Y, m, n, lookup);

//最長共通部分列を見つけます

System.out.println(LCS(X, Y, m, n, lookup));

}

ダウンロードコードを実行する

出力:

MJAU

Python

#文字列`X[0…m-1]`と`Y[0…n-1]`の最長共通部分列を見つける関数

def LCS(X, Y, m, n, lookup):

#は、いずれかのシーケンスの終わりに達した場合、空の文字列を返します

if m == 0 or n == 0:

return str()

# `X`と`Y`の最後の文字が一致する場合は

if X[m - 1] == Y[n - 1]:

#現在の文字(`X[m-1]`または`Y[n-1]`)をのLCSに追加します

#サブストリング`X[0…m-2]`および`Y[0…n-2]`

return LCS(X, Y, m - 1, n - 1, lookup) + X[m - 1]

#それ以外の場合、`X`と`Y`の最後の文字が異なる場合

# 現在のセルの一番上のセルの値が左よりも大きい場合は

#セル、次に文字列 `X`の現在の文字を削除し、LCSを検索します

# 部分文字列`X[0…m-2]`、`Y[0…n-1]`の

if lookup[m - 1][n] > lookup[m][n - 1]:

return LCS(X, Y, m - 1, n, lookup)

else:

# 現在のセルの左側のセルの値が上部よりも大きい場合は

#セル、次に文字列 `Y`の現在の文字を削除し、LCSを検索します

# 部分文字列`X[0…m-1]`、`Y[0…n-2]`の

return LCS(X, Y, m, n - 1, lookup)

#LCSの長さを見つけることによってルックアップテーブルを埋める関数

# サブストリング`X[0…m-1]`および`Y[0…n-1]`の

def LCSLength(X, Y, m, n, lookup):

#はボトムアップ方式でルックアップテーブルを埋めます

for i in range(1, m + 1):

for j in range(1, n + 1):

# `X`と`Y`の現在の文字が一致する場合は

if X[i - 1] == Y[j - 1]:

lookup[i][j] = lookup[i - 1][j - 1] + 1

#それ以外の場合、`X`と`Y`の現在の文字が一致しない場合

else:

lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1])

if __name__ == '__main__':

X = 'XMJYAUZ'

Y = 'MZJAWXU'

m = len(X)

n = len(Y)

# lookup[i][j]は、サブストリング`X[0…i-1]`および`Y[0…j-1]`のLCSの長さを格納します

lookup = [[0 for x in range(n + 1)] for y in range(m + 1)]

#フィルルックアップテーブル

LCSLength(X, Y, m, n, lookup)

#は最長共通部分列を見つけます

print(LCS(X, Y, m, n, lookup))

ダウンロードコードを実行する

出力:

MJAU

可能なすべてのLCSを出力するようにコードを変更するにはどうすればよいですか?

上記のコードは、指定されたシーケンスの最長共通部分列をすべて生成するわけではありません。常に1つのLCSを印刷します。上記のコードの問題は、 X と Y 異なる場合は、の最後の文字のいずれかを破棄します X またはの最後の文字 Y 現在のセルに対する上部または左側のセルの値に基づきます。しかし、LCSが破棄された文字でも可能である場合はどうなりますか?

上のセルが左のセルと等しい場合を除いて、考え方は同じです。両方の文字を考慮してください。それ以外の場合は、より大きな価値の方向に進みます。アルゴリズムは、C++、Java、およびPythonで次のように実装できます。

C++

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <iostream>

#include <vector>

#include <set>

#include <string>

using namespace std;

//部分文字列のすべてのLCSを返す関数`X[0…m-1]`、`Y[0…n-1]`

vector<string> LCS(string X, string Y, int m, int n, auto &lookup)

{

//いずれかのシーケンスの終わりに達した場合

if (m == 0 || n == 0)

{

//空の文字列を使用してvectorを作成し、

return {""};

}

//`X`と`Y`の最後の文字が一致する場合

if (X[m - 1] == Y[n - 1])

{

//`X`と`Y`の最後の文字を無視し、部分文字列のすべてのLCSを検索します

// `X[0…m-2]`、`Y[0…n-2]`そしてそれをvectorに保存します

vector<string> lcs = LCS(X, Y, m - 1, n - 1, lookup);

//現在の文字`X[m-1]`または`Y[n-1]`をのすべてのLCSに追加します

//サブストリング`X[0…m-2]`および`Y[0…n-2]`

for (string &str: lcs) { // `&` を削除しない

str.push_back(X[m - 1]);

}

return lcs;

}

//`X`と`Y`の最後の文字が一致しない場合にここに到達します

//現在のセルの一番上のセルの値が左のセルよりも大きい場合、

//次に、文字列 `X`の現在の文字を無視し、のすべてのLCSを検索します

//サブストリング`X[0…m-2]`、`Y[0…n-1]`

if (lookup[m - 1][n] > lookup[m][n - 1]) {

return LCS(X, Y, m - 1, n, lookup);

}

//現在のセルの左側のセルの値が上部のセルよりも大きい場合、

//次に、文字列 `Y`の現在の文字を無視し、のすべてのLCSを検索します

//サブストリング`X[0…m-1]`、`Y[0…n-2]`

if (lookup[m][n - 1] > lookup[m - 1][n]) {

return LCS(X, Y, m, n - 1, lookup);

}

//上のセルの値が左のセルと等しい場合は、次のことを考慮してください。

//両方の文字

vector<string> top = LCS(X, Y, m - 1, n, lookup);

vector<string> left = LCS(X, Y, m, n - 1, lookup);

// 2つのvectorをマージして、

top.insert(top.end(), left.begin(), left.end());

// copy(left.begin(), left.end(), back_inserter(top));

return top;

}

//LCSの長さを見つけることによってルックアップテーブルを埋める関数

//部分文字列`X[0…m-1]`と`Y[0…n-1]`の

void LCSLength(string X, string Y, int m, int n, auto &lookup)

{

//ルックアップテーブルの最初の行と最初の列はすでに0です

//ルックアップテーブルをボトムアップ方式で入力します

for (int i = 1; i <= m; i++)

{

for (int j = 1; j <= n; j++)

{

//`X`と`Y`の現在の文字が一致する場合

if (X[i - 1] == Y[j - 1]) {

lookup[i][j] = lookup[i - 1][j - 1] + 1;

}

//それ以外の場合、`X`と`Y`の現在の文字が一致しない場合

else {

lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);

}

//文字列`X`と`Y`のすべてのLCSを検索する関数

set<string> LCS(string X, string Y)

{

int m = X.length(), n = Y.length();

// lookup[i][j]は、部分文字列`X[0…i-1]`と`Y[0…j-1]`のLCSの長さを格納します

vector<vector<int>> lookup(m + 1, vector<int>(n + 1));

//ルックアップテーブルを埋めます

LCSLength(X, Y, m, n, lookup);

//最長共通部分列をすべて検索します

vector<string> v = LCS(X, Y, m, n, lookup);

//vectorには重複が含まれる可能性があるため、セットに「変換」します

set<string> lcs(make_move_iterator(v.begin()), make_move_iterator(v.end()));

// to copy a vector to a set use set<string> lcs(v.begin(), v.end())

//すべてのLCSを含むセットを返します

return lcs;

}

int main()

{

string X = "ABCBDAB", Y = "BDCABA";

set<string> lcs = LCS(X, Y);

//セット要素を印刷します

for (string str: lcs) {

cout << str << endl;

}

return 0;

}

ダウンロードコードを実行する

出力:

BCAB
BCBA
BDAB

Java

100

101

102

103

104

105

import java.util.*;

class Main

{

//部分文字列のすべてのLCSを返す関数`X[0…m-1]`、`Y[0…n-1]`

public static List<String> LCS(String X, String Y, int m, int n, int[][] lookup)

{

//いずれかのシーケンスの終わりに達した場合

if (m == 0 || n == 0)

{

// 1つの空の文字列でリストを作成し、

return new ArrayList<>(Collections.nCopies(1, ""));

}

//`X`と`Y`の最後の文字が一致する場合

if (X.charAt(m - 1) == Y.charAt(n - 1))

{

//`X`と`Y`の最後の文字を無視し、のすべてのLCSを検索します

//サブストリング`X[0…m-2]`、`Y[0…n-2]`そしてそれをリストに保存します

List<String> lcs = LCS(X, Y, m - 1, n - 1, lookup);

//現在の文字`X[m-1]`または`Y[n-1]`を追加します

//部分文字列`X[0…m-2]`と`Y[0…n-2]`のすべてのLCSに

for (int i = 0; i < lcs.size(); i++) {

lcs.set(i, lcs.get(i) + (X.charAt(m - 1)));

}

return lcs;

}

//`X`と`Y`の最後の文字が一致しない場合にここに到達します

//現在のセルの一番上のセルの値が左のセルよりも大きい場合、

//次に、文字列 `X`の現在の文字を無視し、のすべてのLCSを検索します

//サブストリング`X[0…m-2]`、`Y[0…n-1]`

if (lookup[m - 1][n] > lookup[m][n - 1]) {

return LCS(X, Y, m - 1, n, lookup);

}

//現在のセルの左側のセルの値が上部のセルよりも大きい場合、

//次に、文字列 `Y`の現在の文字を無視し、のすべてのLCSを検索します

//サブストリング`X[0…m-1]`、`Y[0…n-2]`

if (lookup[m][n - 1] > lookup[m - 1][n]) {

return LCS(X, Y, m, n - 1, lookup);

}

//上のセルの値が左のセルと等しい場合、

//次に両方の文字を検討します

List<String> top = LCS(X, Y, m - 1, n, lookup);

List<String> left = LCS(X, Y, m, n - 1, lookup);

// 2つのリストをマージして、

top.addAll(left);

return top;

}

//LCSの長さを見つけることによってルックアップテーブルを埋める関数

//部分文字列`X`と`Y`の

public static void LCSLength(String X, String Y, int[][] lookup)

{

//ルックアップテーブルをボトムアップ方式で入力します

for (int i = 1; i <= X.length(); i++)

{

for (int j = 1; j <= Y.length(); j++)

{

//`X`と`Y`の現在の文字が一致する場合

if (X.charAt(i - 1) == Y.charAt(j - 1)) {

lookup[i][j] = lookup[i - 1][j - 1] + 1;

}

//それ以外の場合、`X`と`Y`の現在の文字が一致しない場合

else {

lookup[i][j] = Integer.max(lookup[i - 1][j], lookup[i][j - 1]);

}

//文字列`X[0…m-1]`と`Y[0…n-1]`のすべてのLCSを検索する関数

public static Set<String> LCS(String X, String Y, int[][] lookup)

{

//ルックアップテーブルを埋めます

LCSLength(X, Y, lookup);

//最長共通部分列をすべて検索します

List<String> lcs = LCS(X, Y, X.length(), Y.length(), lookup);

//リストには重複が含まれている可能性があるため、リストをセットに「変換」して戻ります

return new HashSet<>(lcs);

}

public static void main(String[] args)

{

String X = "ABCBDAB", Y = "BDCABA";

// lookup[i][j]は、部分文字列`X[0…i-1]`と`Y[0…j-1]`のLCSの長さを格納します

int[][] lookup = new int[X.length() + 1][Y.length() + 1];

Set<String> lcs = LCS(X, Y, lookup);

//セット要素を印刷します

System.out.println(lcs);

}

ダウンロードコードを実行する

出力:

[BCAB, BCBA, BDAB]

Python

#部分文字列`X[0…m-1]`、`Y[0…n-1]`のすべてのLCSを返す関数

def LCS(X, Y, m, n, lookup):

# いずれかのシーケンスの終わりに達した場合は

if m == 0 or n == 0:

#は、1つの空の文字列を含むリストを作成し、

return ['']

# `X`と`Y`の最後の文字が一致する場合は

if X[m - 1] == Y[n - 1]:

#は、`X`と`Y`の最後の文字を無視し、部分文字列のすべてのLCSを検索します

# `X[0…m-2]`、`Y[0…n-2]`そしてそれをリストに保存します

lcs = LCS(X, Y, m - 1, n - 1, lookup)

#は現在の文字`X[m-1]`または`Y[n-1]`を追加します

# サブストリング`X[0…m-2]`および`Y[0…n-2]`のすべてのLCSへの

for i in range(len(lcs)):

lcs[i] = lcs[i] + (X[m - 1])

return lcs

#`X`と`Y`の最後の文字が一致しない場合にここに到達します

#現在のセルの一番上のセルの値が左のセルよりも大きい場合、

#は、文字列 `X`の現在の文字を無視し、のすべてのLCSを検索します。

#サブストリング`X[0…m-2]`、`Y[0…n-1]`

if lookup[m - 1][n] > lookup[m][n - 1]:

return LCS(X, Y, m - 1, n, lookup)

#現在のセルの左側のセルの値が上部のセルよりも大きい場合、

#は、文字列 `Y`の現在の文字を無視し、のすべてのLCSを検索します。

#サブストリング`X[0…m-1]`、`Y[0…n-2]`

if lookup[m][n - 1] > lookup[m - 1][n]:

return LCS(X, Y, m, n - 1, lookup)

#上のセルの値が左のセルと等しい場合は、両方の文字を考慮してください

top = LCS(X, Y, m - 1, n, lookup)

left = LCS(X, Y, m, n - 1, lookup)

#は2つのリストをマージし、

return top + left

#LCSの長さを見つけることによってルックアップテーブルを埋める関数

# 部分文字列`X`と`Y`の

def LCSLength(X, Y, lookup):

#はボトムアップ方式でルックアップテーブルを埋めます

for i in range(1, len(X) + 1):

for j in range(1, len(Y) + 1):

# `X`と`Y`の現在の文字が一致する場合は

if X[i - 1] == Y[j - 1]:

lookup[i][j] = lookup[i - 1][j - 1] + 1

#それ以外の場合、`X`と`Y`の現在の文字が一致しない場合

else:

lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1])

#文字列`X[0…m-1]`と`Y[0…n-1]`のすべてのLCSを検索する関数

def findLCS(X, Y):

# lookup[i][j]は、サブストリング`X[0…i-1]`および`Y[0…j-1]`のLCSの長さを格納します

lookup = [[0 for x in range(len(Y) + 1)] for y in range(len(X) + 1)]

#フィルルックアップテーブル

LCSLength(X, Y, lookup)

#は、最長共通部分列をすべて検索します

lcs = LCS(X, Y, len(X), len(Y), lookup)

#リストには重複が含まれている可能性があるため、リストをセットに「変換」して戻ります

return set(lcs)

if __name__ == '__main__':

X = 'ABCBDAB'

Y = 'BDCABA'

lcs = findLCS(X, Y)

print(lcs)

ダウンロードコードを実行する

出力:

{‘BCBA’, ‘BDAB’, ‘BCAB’}

参照： https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

最長共通部分列|すべてのLCSを検索する

C++

Java

Python

C++

Java

Python