原文:
给定两个序列，打印两个序列中最长的子序列。 例: lcs 对于输入序列“abcdgh”和“aedfhr”是长度为 3 的“adh”。 lcs 对于输入序列“aggtab”和“gxtxayb”是长度为 4 的“gtab”。 我们在中讨论了 的问题。那里讨论的函数主要是求 lcs 的长度。为了求出 lcs 的长度，构造了一个 2d 表 l[][]。在这篇文章中，讨论了构建和打印 lcs 的功能。 以下是打印 lcs 的详细算法。它使用相同的 2d 表 l[][]。 1) 使用中讨论的步骤构建 l[m 1][n 1]。 2) 值 l[m][n]包含 lcs 长度。创建一个长度等于 lcs 加 1 的字符数组 lcs。 2) 从 l[m][n]开始遍历 2d 阵。对每个单元格 l[i][j] 执行以下操作….. a) 如果对应于 l[i][j]的字符(在 x 和 y 中)相同(或 x[i-1] == y[j-1])，则包括该字符作为 lcs 的一部分。 ….. b) 否则比较 l[i-1][j]和 l[i][j-1]的值，向更大的值的方向走。 下表(取自)显示了上述算法遵循的步骤(高亮显示)。
| | zero | one | two | three | four | five | six | seven | | 一座岛 | m | z | j | a | w | x | u | | zero | 一座岛 | **0** | zero | zero | zero | zero | zero | zero | zero | | one | x | zero | zero | zero | zero | zero | zero | one | one | | two | m | zero | **1** | one | one | one | one | one | one | | three | j | zero | one | one | **2** | two | two | two | two | | four | y | zero | one | one | two | two | two | two | two | | five | a | zero | one | one | two | **3** | three | three | three | | six | u | zero | one | one | two | three | three | three | **4** | | seven | z | zero | one | two | two | three | three | three | four | 下面是上述方法的实现。 ## c/* dynamic programming implementation of lcs problem */
#include
#include
#include
using namespace std;
/* returns length of lcs for x[0..m-1], y[0..n-1] */
void lcs( char *x, char *y, int m, int n )
{
int l[m 1][n 1];
/* following steps build l[m 1][n 1] in bottom up fashion. note
that l[i][j] contains length of lcs of x[0..i-1] and y[0..j-1] */
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]);
}
}
// following code is used to print lcs
int index = l[m][n];
// create a character array to store the lcs string
char lcs[index 1];
lcs[index] = '\0'; // set the terminating character
// start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int i = m, j = n;
while (i > 0 && j > 0)
{
// if current character in x[] and y are same, then
// current character is part of lcs
if (x[i-1] == y[j-1])
{
lcs[index-1] = x[i-1]; // put current character in result
i--; j--; index--; // reduce values of i, j and index
}
// if not same, then find the larger of two and
// go in the direction of larger value
else if (l[i-1][j] > l[i][j-1])
i--;
else
j--;
}
// print the lcs
cout << "lcs of " << x << " and " << y << " is " << lcs;
}
/* driver program to test above function */
int main()
{
char x[] = "aggtab";
char y[] = "gxtxayb";
int m = strlen(x);
int n = strlen(y);
lcs(x, y, m, n);
return 0;
}
// dynamic programming implementation of lcs problem in java
import java.io.*;
class longestcommonsubsequence
{
// returns length of lcs for x[0..m-1], y[0..n-1]
static void lcs(string x, string y, int m, int n)
{
int[][] l = new int[m 1][n 1];
// following steps build l[m 1][n 1] in bottom up fashion. note
// that l[i][j] contains length of lcs of x[0..i-1] and y[0..j-1]
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]);
}
}
// following code is used to print lcs
int index = l[m][n];
int temp = index;
// create a character array to store the lcs string
char[] lcs = new char[index 1];
lcs[index] = '\u0000'; // set the terminating character
// start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int i = m;
int j = n;
while (i > 0 && j > 0)
{
// if current character in x[] and y are same, then
// current character is part of lcs
if (x.charat(i-1) == y.charat(j-1))
{
// put current character in result
lcs[index-1] = x.charat(i-1);
// reduce values of i, j and index
i--;
j--;
index--;
}
// if not same, then find the larger of two and
// go in the direction of larger value
else if (l[i-1][j] > l[i][j-1])
i--;
else
j--;
}
// print the lcs
system.out.print("lcs of " x " and " y " is ");
for(int k=0;k<=temp;k )
system.out.print(lcs[k]);
}
// driver program
public static void main (string[] args)
{
string x = "aggtab";
string y = "gxtxayb";
int m = x.length();
int n = y.length();
lcs(x, y, m, n);
}
}
// contributed by pramod kumar
# dynamic programming implementation of lcs problem
# returns length of lcs for x[0..m-1], y[0..n-1]
def lcs(x, y, m, n):
l = [[0 for x in xrange(n 1)] for x in xrange(m 1)]
# following steps build l[m 1][n 1] in bottom up fashion. note
# that l[i][j] contains length of lcs of x[0..i-1] and y[0..j-1]
for i in xrange(m 1):
for j in xrange(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])
# following code is used to print lcs
index = l[m][n]
# create a character array to store the lcs string
lcs = [""] * (index 1)
lcs[index] = ""
# start from the right-most-bottom-most corner and
# one by one store characters in lcs[]
i = m
j = n
while i > 0 and j > 0:
# if current character in x[] and y are same, then
# current character is part of lcs
if x[i-1] == y[j-1]:
lcs[index-1] = x[i-1]
i-=1
j-=1
index-=1
# if not same, then find the larger of two and
# go in the direction of larger value
elif l[i-1][j] > l[i][j-1]:
i-=1
else:
j-=1
print "lcs of " x " and " y " is " "".join(lcs)
# driver program
x = "aggtab"
y = "gxtxayb"
m = len(x)
n = len(y)
lcs(x, y, m, n)
# this code is contributed by bhavya jain
// dynamic programming implementation
// of lcs problem in c#
using system;
class gfg
{
// returns length of lcs for x[0..m-1], y[0..n-1]
static void lcs(string x, string y, int m, int n)
{
int[,] l = new int[m 1, n 1];
// following steps build l[m 1][n 1] in
// bottom up fashion. note that l[i][j]
// contains length of lcs of x[0..i-1]
// and y[0..j-1]
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]);
}
}
// following code is used to print lcs
int index = l[m, n];
int temp = index;
// create a character array
// to store the lcs string
char[] lcs = new char[index 1];
// set the terminating character
lcs[index] = '\0';
// start from the right-most-bottom-most corner
// and one by one store characters in lcs[]
int k = m, l = n;
while (k > 0 && l > 0)
{
// if current character in x[] and y
// are same, then current character
// is part of lcs
if (x[k-1] == y[l-1])
{
// put current character in result
lcs[index-1] = x[k-1];
// reduce values of i, j and index
k--;
l--;
index--;
}
// if not same, then find the larger of two and
// go in the direction of larger value
else if (l[k-1, l] > l[k, l-1])
k--;
else
l--;
}
// print the lcs
console.write("lcs of " x " and " y " is ");
for(int q = 0; q <= temp; q )
console.write(lcs[q]);
}
// driver program
public static void main ()
{
string x = "aggtab";
string y = "gxtxayb";
int m = x.length;
int n = y.length;
lcs(x, y, m, n);
}
}
// this code is contributed by sam007
0 && $j > 0)
{
// if current character in x[] and y are same,
// then current character is part of lcs
if ($x[$i - 1] == $y[$j - 1])
{
// put current character in result
$lcs[$index - 1] = $x[$i - 1];
$i--;
$j--;
$index--; // reduce values of i, j and index
}
// if not same, then find the larger of two
// and go in the direction of larger value
else if ($l[$i - 1][$j] > $l[$i][$j - 1])
$i--;
else
$j--;
}
// print the lcs
echo "lcs of " . $x . " and " . $y . " is ";
for($k = 0; $k < $temp; $k )
echo $lcs[$k];
}
// driver code
$x = "aggtab";
$y = "gxtxayb";
$m = strlen($x);
$n = strlen($y);
lcs($x, $y, $m, $n);
// this code is contributed by ita_c
?>
lcs of aggtab and gxtxayb is gtab
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
