原文:
给定两个序列，打印两个序列中所有最长的子序列。 例:
input:
string x = "agtgatg"
string y = "gttag"
output:
gtag
gttg
input:
string x = "aatcc"
string y = "acacg"
output:
acc
aac
input:
string x = "abcbdab"
string y = "bdcaba"
output:
bcab
bcba
bdab
我们在这里讨论了最长公共子序列(lcs)问题。那里讨论的函数主要是求 lcs 的长度。我们还讨论了如何打印最长的子序列。但是由于 lcs 对于两个字符串并不是唯一的，在这篇文章中我们将打印出 lcs 问题的所有可能的pg电子试玩链接的解决方案。 下面是打印全 lcs 的详细算法。 我们构建 l[m 1][n 1]表，如帖子中所述，并从 l[m][n]开始遍历 2d 阵列。对于矩阵中的当前单元格 l[i][j]， a)如果 x 和 y 的最后一个字符相同(即 x[i-1] == y[j-1])，则该字符必须出现在子串 x[0…i-1]和 y[0]的所有 lcs 中..j-1]。我们简单地在矩阵中递归 l[i-1][j-1]，并将当前字符附加到子串 x[0…i-2]和 y[0]的所有 lcs 可能值上..j-2]。 b)如果 x 和 y 的最后一个字符不相同(即 x[i-1]！= y[j-1])，那么根据哪个值更大，可以从矩阵的顶部(即 l[i-1][j])或从矩阵的左侧(即 l[i][j-1])构造 lcs。如果两个值相等(即 l[i-1][j] == l[i][j-1])，则从矩阵的两边构造。所以基于 l[i-1][j]和 l[i][j-1]的值，我们往更大值的方向走，或者如果值相等，往两个方向走。 以下是上述思想的递归实现–
c
/* dynamic programming implementation of lcs problem */
#include
using namespace std;
// maximum string length
#define n 100
int l[n][n];
/* returns set containing all lcs for x[0..m-1], y[0..n-1] */
set findlcs(string x, string y, int m, int n)
{
// construct a set to store possible lcs
set s;
// if we reaches end of either string, return
// a empty set
if (m == 0 || n == 0)
{
s.insert("");
return s;
}
// if the last characters of x and y are same
if (x[m - 1] == y[n - 1])
{
// recurse for x[0..m-2] and y[0..n-2] in
// the matrix
set tmp = findlcs(x, y, m - 1, n - 1);
// append current character to all possible lcs
// of substring x[0..m-2] and y[0..n-2].
for (string str : tmp)
s.insert(str x[m - 1]);
}
// if the last characters of x and y are not same
else
{
// if lcs can be constructed from top side of
// the matrix, recurse for x[0..m-2] and y[0..n-1]
if (l[m - 1][n] >= l[m][n - 1])
s = findlcs(x, y, m - 1, n);
// if lcs can be constructed from left side of
// the matrix, recurse for x[0..m-1] and y[0..n-2]
if (l[m][n - 1] >= l[m - 1][n])
{
set tmp = findlcs(x, y, m, n - 1);
// merge two sets if l[m-1][n] == l[m][n-1]
// note s will be empty if l[m-1][n] != l[m][n-1]
s.insert(tmp.begin(), tmp.end());
}
}
return s;
}
/* returns length of lcs for x[0..m-1], y[0..n-1] */
int lcs(string x, string y, int m, int n)
{
// build l[m 1][n 1] in bottom up fashion
for (int i = 0; i <= m; i )
{
for (int j = 0; j <= n; j )
{
if (i == 0 || j == 0)
l[i][j] = 0;
else if (x[i - 1] == y[j - 1])
l[i][j] = l[i - 1][j - 1] 1;
else
l[i][j] = max(l[i - 1][j], l[i][j - 1]);
}
}
return l[m][n];
}
/* driver program to test above function */
int main()
{
string x = "agtgatg";
string y = "gttag";
int m = x.length();
int n = y.length();
cout << "lcs length is " << lcs(x, y, m, n) << endl;
set s = findlcs(x, y, m, n);
for (string str : s)
cout << str << endl;
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
/* dynamic programming implementation of lcs problem */
import java.util.*;
class gfg
{
// maximum string length
static int n = 100;
static int [][]l = new int[n][n];
/* returns set containing all lcs for
x[0..m-1], y[0..n-1] */
static set findlcs(string x,
string y, int m, int n)
{
// construct a set to store possible lcs
set s = new hashset<>();
// if we reaches end of either string,
// return a empty set
if (m == 0 || n == 0)
{
s.add("");
return s;
}
// if the last characters of x and y are same
if (x.charat(m - 1) == y.charat(n - 1))
{
// recurse for x[0..m-2] and y[0..n-2]
// in the matrix
set tmp = findlcs(x, y, m - 1, n - 1);
// append current character to all possible lcs
// of substring x[0..m-2] and y[0..n-2].
for (string str : tmp)
s.add(str x.charat(m - 1));
}
// if the last characters of x and y are not same
else
{
// if lcs can be constructed from top side of
// the matrix, recurse for x[0..m-2] and y[0..n-1]
if (l[m - 1][n] >= l[m][n - 1])
s = findlcs(x, y, m - 1, n);
// if lcs can be constructed from left side of
// the matrix, recurse for x[0..m-1] and y[0..n-2]
if (l[m][n - 1] >= l[m - 1][n])
{
set tmp = findlcs(x, y, m, n - 1);
// merge two sets if l[m-1][n] == l[m][n-1]
// note s will be empty if l[m-1][n] != l[m][n-1]
s.addall(tmp);
}
}
return s;
}
/* returns length of lcs for x[0..m-1], y[0..n-1] */
static int lcs(string x, string y, int m, int n)
{
// build l[m 1][n 1] in bottom up fashion
for (int i = 0; i <= m; i )
{
for (int j = 0; j <= n; j )
{
if (i == 0 || j == 0)
l[i][j] = 0;
else if (x.charat(i - 1) == y.charat(j - 1))
l[i][j] = l[i - 1][j - 1] 1;
else
l[i][j] = math.max(l[i - 1][j],
l[i][j - 1]);
}
}
return l[m][n];
}
// driver code
public static void main(string[] args)
{
string x = "agtgatg";
string y = "gttag";
int m = x.length();
int n = y.length();
system.out.println("lcs length is "
lcs(x, y, m, n));
set s = findlcs(x, y, m, n);
for (string str : s)
system.out.println(str);
}
}
// this code is contributed by 29ajaykumar
python 3
# dynamic programming implementation of lcs problem
# maximum string length
n = 100
l = [[0 for i in range(n)]
for j in range(n)]
# returns set containing all lcs
# for x[0..m-1], y[0..n-1]
def findlcs(x, y, m, n):
# construct a set to store possible lcs
s = set()
# if we reaches end of either string, return
# a empty set
if m == 0 or n == 0:
s.add("")
return s
# if the last characters of x and y are same
if x[m - 1] == y[n - 1]:
# recurse for x[0..m-2] and y[0..n-2] in
# the matrix
tmp = findlcs(x, y, m - 1, n - 1)
# append current character to all possible lcs
# of substring x[0..m-2] and y[0..n-2].
for string in tmp:
s.add(string x[m - 1])
# if the last characters of x and y are not same
else:
# if lcs can be constructed from top side of
# the matrix, recurse for x[0..m-2] and y[0..n-1]
if l[m - 1][n] >= l[m][n - 1]:
s = findlcs(x, y, m - 1, n)
# if lcs can be constructed from left side of
# the matrix, recurse for x[0..m-1] and y[0..n-2]
if l[m][n - 1] >= l[m - 1][n]:
tmp = findlcs(x, y, m, n - 1)
# merge two sets if l[m-1][n] == l[m][n-1]
# note s will be empty if l[m-1][n] != l[m][n-1]
for i in tmp:
s.add(i)
return s
# returns length of lcs for x[0..m-1], y[0..n-1]
def lcs(x, y, m, n):
# build l[m 1][n 1] in bottom up fashion
for i in range(m 1):
for j in range(n 1):
if i == 0 or j == 0:
l[i][j] = 0
elif x[i - 1] == y[j - 1]:
l[i][j] = l[i - 1][j - 1] 1
else:
l[i][j] = max(l[i - 1][j],
l[i][j - 1])
return l[m][n]
# driver code
if __name__ == "__main__":
x = "agtgatg"
y = "gttag"
m = len(x)
n = len(y)
print("lcs length is", lcs(x, y, m, n))
s = findlcs(x, y, m, n)
for i in s:
print(i)
# this code is contributed by
# sanjeev2552
c
// dynamic programming implementation
// of lcs problem
using system;
using system.collections.generic;
class gfg
{
// maximum string length
static int n = 100;
static int [,]l = new int[n, n];
/* returns set containing all lcs for
x[0..m-1], y[0..n-1] */
static hashset findlcs(string x,
string y,
int m, int n)
{
// construct a set to store possible lcs
hashset s = new hashset();
// if we reaches end of either string,
// return a empty set
if (m == 0 || n == 0)
{
s.add("");
return s;
}
// if the last characters of x and y are same
if (x[m - 1] == y[n - 1])
{
// recurse for x[0..m-2] and y[0..n-2]
// in the matrix
hashset tmp = findlcs(x, y, m - 1, n - 1);
// append current character to all possible lcs
// of substring x[0..m-2] and y[0..n-2].
foreach (string str in tmp)
s.add(str x[m - 1]);
}
// if the last characters of x and y are not same
else
{
// if lcs can be constructed from top side of
// the matrix, recurse for x[0..m-2] and y[0..n-1]
if (l[m - 1, n] >= l[m, n - 1])
s = findlcs(x, y, m - 1, n);
// if lcs can be constructed from left side of
// the matrix, recurse for x[0..m-1] and y[0..n-2]
if (l[m, n - 1] >= l[m - 1, n])
{
hashset tmp = findlcs(x, y, m, n - 1);
// merge two sets if l[m-1,n] == l[m,n-1]
// note s will be empty if l[m-1,n] != l[m,n-1]
foreach (string str in tmp)
s.add(str);
}
}
return s;
}
/* returns length of lcs for x[0..m-1], y[0..n-1] */
static int lcs(string x, string y, int m, int n)
{
// build l[m 1,n 1] in bottom up fashion
for (int i = 0; i <= m; i )
{
for (int j = 0; j <= n; j )
{
if (i == 0 || j == 0)
l[i, j] = 0;
else if (x[i - 1] == y[j - 1])
l[i, j] = l[i - 1, j - 1] 1;
else
l[i, j] = math.max(l[i - 1, j],
l[i, j - 1]);
}
}
return l[m, n];
}
// driver code
public static void main(string[] args)
{
string x = "agtgatg";
string y = "gttag";
int m = x.length;
int n = y.length;
console.writeline("lcs length is "
lcs(x, y, m, n));
hashset s = findlcs(x, y, m, n);
foreach (string str in s)
console.writeline(str);
}
}
// this code is contributed by rajput-ji
java 描述语言
输出:
lcs length is 4
gtag
gttg
参考资料: 本文由阿迪蒂亚·戈尔供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
