原文:
给定两个字符串 x 和 y，打印同时具有 x 和 y 作为子序列的最短字符串。如果存在多个最短超序列，请打印其中任何一个。 例:
input: x = "aggtab", y = "gxtxayb"
output: "agxgtxayb" or "aggxtxayb"
or any string that represents shortest
supersequence of x and y
input: x = "hello", y = "geek"
output: "gehekllo" or "gheekllo"
or any string that represents shortest
supersequence of x and y
我们已经讨论了如何打印两个给定字符串的最短可能超序列长度。在这篇文章中，我们打印了最短的超序列。 我们已经在下面讨论了在之前的后 中寻找最短超序列长度的算法
let x[0..m-1] and y[0..n-1] be two strings and m and be respective
lengths.
if (m == 0) return n;
if (n == 0) return m;
// if last characters are same, then add 1 to result and
// recur for x[]
if (x[m-1] == y[n-1])
return 1 scs(x, y, m-1, n-1);
// else find shortest of following two
// a) remove last character from x and recur
// b) remove last character from y and recur
else return 1 min( scs(x, y, m-1, n), scs(x, y, m, n-1) );
下表显示了如果我们使用动态编程对字符串 x =“aggtab”和 y =“gxtxayb”、 进行自下而上的求解，则上述算法遵循的步骤
使用 dp pg电子试玩链接的解决方案矩阵，我们可以按照以下步骤– 轻松打印两个字符串的最短超序列
we start from the bottom-right most cell of the matrix and
push characters in output string based on below rules-
1\. if the characters corresponding to current cell (i, j)
in x and y are same, then the character is part of shortest
supersequence. we append it in output string and move
diagonally to next cell (i.e. (i - 1, j - 1)).
2\. if the characters corresponding to current cell (i, j)
in x and y are different, we have two choices -
if matrix[i - 1][j] > matrix[i][j - 1],
we add character corresponding to current
cell (i, j) in string y in output string
and move to the left cell i.e. (i, j - 1)
else
we add character corresponding to current
cell (i, j) in string x in output string
and move to the top cell i.e. (i - 1, j)
3\. if string y reaches its end i.e. j = 0, we add remaining
characters of string x in the output string
else if string x reaches its end i.e. i = 0, we add
remaining characters of string y in the output string.
以下是上述想法的实现–
c
/* a dynamic programming based c program print
shortest supersequence of two strings */
#include
using namespace std;
// returns shortest supersequence of x and y
string printshortestsuperseq(string x, string y)
{
int m = x.length();
int n = y.length();
// dp[i][j] contains length of shortest supersequence
// for x[0..i-1] and y[0..j-1]
int dp[m 1][n 1];
// fill table in bottom up manner
for (int i = 0; i <= m; i )
{
for (int j = 0; j <= n; j )
{
// below steps follow recurrence relation
if(i == 0)
dp[i][j] = j;
else if(j == 0)
dp[i][j] = i;
else if(x[i - 1] == y[j - 1])
dp[i][j] = 1 dp[i - 1][j - 1];
else
dp[i][j] = 1 min(dp[i - 1][j], dp[i][j - 1]);
}
}
// following code is used to print shortest supersequence
// dp[m][n] stores the length of the shortest supersequence
// of x and y
// string to store the shortest supersequence
string str;
// start from the bottom right corner and one by one
// push characters in output string
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 shortest supersequence
if (x[i - 1] == y[j - 1])
{
// put current character in result
str.push_back(x[i - 1]);
// reduce values of i, j and index
i--, j--;
}
// if current character in x and y are different
else if (dp[i - 1][j] > dp[i][j - 1])
{
// put current character of y in result
str.push_back(y[j - 1]);
// reduce values of j and index
j--;
}
else
{
// put current character of x in result
str.push_back(x[i - 1]);
// reduce values of i and index
i--;
}
}
// if y reaches its end, put remaining characters
// of x in the result string
while (i > 0)
{
str.push_back(x[i - 1]);
i--;
}
// if x reaches its end, put remaining characters
// of y in the result string
while (j > 0)
{
str.push_back(y[j - 1]);
j--;
}
// reverse the string and return it
reverse(str.begin(), str.end());
return str;
}
// driver program to test above function
int main()
{
string x = "aggtab";
string y = "gxtxayb";
cout << printshortestsuperseq(x, y);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
/* a dynamic programming based java program print
shortest supersequence of two strings */
class gfg {
// returns shortest supersequence of x and y
static string printshortestsuperseq(string x, string y)
{
int m = x.length();
int n = y.length();
// dp[i][j] contains length of
// shortest supersequence
// for x[0..i-1] and y[0..j-1]
int dp[][] = new int[m 1][n 1];
// fill table in bottom up manner
for (int i = 0; i <= m; i )
{
for (int j = 0; j <= n; j )
{
// below steps follow recurrence relation
if (i == 0)
{
dp[i][j] = j;
}
else if (j == 0)
{
dp[i][j] = i;
}
else if (x.charat(i - 1) == y.charat(j - 1))
{
dp[i][j] = 1 dp[i - 1][j - 1];
}
else
{
dp[i][j] = 1 math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// following code is used to print
// shortest supersequence dp[m][n] s
// tores the length of the shortest
// supersequence of x and y
// string to store the shortest supersequence
string str = "";
// start from the bottom right corner and one by one
// push characters in output string
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 shortest supersequence
if (x.charat(i - 1) == y.charat(j - 1))
{
// put current character in result
str = (x.charat(i - 1));
// reduce values of i, j and index
i--;
j--;
}
// if current character in x and y are different
else if (dp[i - 1][j] > dp[i][j - 1])
{
// put current character of y in result
str = (y.charat(j - 1));
// reduce values of j and index
j--;
}
else
{
// put current character of x in result
str = (x.charat(i - 1));
// reduce values of i and index
i--;
}
}
// if y reaches its end, put remaining characters
// of x in the result string
while (i > 0)
{
str = (x.charat(i - 1));
i--;
}
// if x reaches its end, put remaining characters
// of y in the result string
while (j > 0)
{
str = (y.charat(j - 1));
j--;
}
// reverse the string and return it
str = reverse(str);
return str;
}
static string reverse(string input)
{
char[] temparray = input.tochararray();
int left, right = 0;
right = temparray.length - 1;
for (left = 0; left < right; left , right--)
{
// swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return string.valueof(temparray);
}
// driver code
public static void main(string[] args)
{
string x = "aggtab";
string y = "gxtxayb";
system.out.println(printshortestsuperseq(x, y));
}
}
// this code is contributed by 29ajaykumar
python 3
# a dynamic programming based python3 program print
# shortest supersequence of two strings
# returns shortest supersequence of x and y
def printshortestsuperseq(x, y):
m = len(x)
n = len(y)
# dp[i][j] contains length of shortest
# supersequence for x[0..i-1] and y[0..j-1]
dp = [[0 for i in range(n 1)]
for j in range(n 1)]
# fill table in bottom up manner
for i in range(m 1):
for j in range(n 1):
# below steps follow recurrence relation
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif x[i - 1] == y[j - 1]:
dp[i][j] = 1 dp[i - 1][j - 1]
else:
dp[i][j] = 1 min(dp[i - 1][j],
dp[i][j - 1])
# following code is used to print
# shortest supersequence
# dp[m][n] stores the length of the
# shortest supersequence of x and y
# string to store the shortest supersequence
string = ""
# start from the bottom right corner and
# one by one push characters in output string
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
# shortest supersequence
if x[i - 1] == y[j - 1]:
# put current character in result
string = x[i - 1]
# reduce values of i, j and index
i -= 1
j -= 1
# if current character in x and y are different
elif dp[i - 1][j] > dp[i][j - 1]:
# put current character of y in result
string = y[j - 1]
# reduce values of j and index
j -= 1
else:
# put current character of x in result
string = x[i - 1]
# reduce values of i and index
i -= 1
# if y reaches its end, put remaining characters
# of x in the result string
while i > 0:
string = x[i - 1]
i -= 1
# if x reaches its end, put remaining characters
# of y in the result string
while j > 0:
string = y[j - 1]
j -= 1
string = list(string)
# reverse the string and return it
string.reverse()
return ''.join(string)
# driver code
if __name__ == "__main__":
x = "aggtab"
y = "gxtxayb"
print(printshortestsuperseq(x, y))
# this code is contributed by
# sanjeev2552
c
/* a dynamic programming based c# program print
shortest supersequence of two strings */
using system;
class gfg
{
// returns shortest supersequence of x and y
static string printshortestsuperseq(string x, string y)
{
int m = x.length;
int n = y.length;
// dp[i,j] contains length of
// shortest supersequence
// for x[0..i-1] and y[0..j-1]
int [,]dp = new int[m 1, n 1];
int i, j;
// fill table in bottom up manner
for (i = 0; i <= m; i )
{
for (j = 0; j <= n; j )
{
// below steps follow recurrence relation
if (i == 0)
{
dp[i, j] = j;
}
else if (j == 0)
{
dp[i, j] = i;
}
else if (x[i - 1] == y[j - 1])
{
dp[i, j] = 1 dp[i - 1, j - 1];
}
else
{
dp[i, j] = 1 math.min(dp[i - 1, j], dp[i, j - 1]);
}
}
}
// following code is used to print
// shortest supersequence dp[m,n] s
// tores the length of the shortest
// supersequence of x and y
// string to store the shortest supersequence
string str = "";
// start from the bottom right corner and one by one
// push characters in output string
i = m; j = n;
while (i > 0 && j > 0)
{
// if current character in x and y are same, then
// current character is part of shortest supersequence
if (x[i - 1] == y[j - 1])
{
// put current character in result
str = (x[i - 1]);
// reduce values of i, j and index
i--;
j--;
}
// if current character in x and y are different
else if (dp[i - 1, j] > dp[i, j - 1])
{
// put current character of y in result
str = (y[j - 1]);
// reduce values of j and index
j--;
}
else
{
// put current character of x in result
str = (x[i - 1]);
// reduce values of i and index
i--;
}
}
// if y reaches its end, put remaining characters
// of x in the result string
while (i > 0)
{
str = (x[i - 1]);
i--;
}
// if x reaches its end, put remaining characters
// of y in the result string
while (j > 0)
{
str = (y[j - 1]);
j--;
}
// reverse the string and return it
str = reverse(str);
return str;
}
static string reverse(string input)
{
char[] temparray = input.tochararray();
int left, right = 0;
right = temparray.length - 1;
for (left = 0; left < right; left , right--)
{
// swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return string.join("",temparray);
}
// driver code
public static void main(string[] args)
{
string x = "aggtab";
string y = "gxtxayb";
console.writeline(printshortestsuperseq(x, y));
}
}
/* this code has been contributed
by princiraj1992*/
java 描述语言
output
agxgtxayb
上述解的时间复杂度为 o(n 2 )。 程序使用的辅助空间为 o(n 2 )。 本文由阿迪蒂亚·戈尔供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
