给定两个序列，打印两个序列中存在的所有最长子序列。 例如：
null
Input: string X = "AGTGATG"string Y = "GTTAG"Output: GTAGGTTGInput: string X = "AATCC"string Y = "ACACG"Output: ACCAACInput: string X = "ABCBDAB"string Y = "BDCABA"Output: BCABBCBABDAB
我们讨论了最长公共子序列（LCS）问题 在这里 .这里讨论的功能主要是找到LCS的长度。我们还讨论了如何打印最长的子序列 在这里 但由于两个字符串的LCS不是唯一的，在这篇文章中，我们将打印出LCS问题的所有可能解决方案。 以下是打印所有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…j-1]的所有LCS中。我们只是在矩阵中递归L[i-1][j-1]，并将当前字符附加到子串X[0…i-2]和Y[0…j-2]的所有可能的LCS中。 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 <bits/stdc++.h> 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<string> findLCS(string X, string Y, int m, int n) { // construct a set to store possible LCS set<string> 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<string> 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<string> 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<string> 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<String> findLCS(String X, String Y, int m, int n) { // construct a set to store possible LCS Set<String> 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<String> 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<String> 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<String> s = findLCS(X, Y, m, n); for (String str : s) System.out.println(str); } } // This code is contributed by 29AjayKumar |
Python3
# 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 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 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<String> findLCS(String X, String Y, int m, int n) { // construct a set to store possible LCS HashSet<String> s = new HashSet<String>(); // 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<String> 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<String> 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<String> s = findLCS(X, Y, m, n); foreach (String str in s) Console.WriteLine(str); } } // This code is contributed by Rajput-Ji |
Javascript
<script> /* Dynamic Programming implementation of LCS problem */ // Maximum String length let N = 100; let L = new Array(N); for (let i=0;i<N;i++) { L[i]= new Array(N); } /* Returns set containing all LCS for X[0..m-1], Y[0..n-1] */ function findLCS(X,Y,m,n) { // construct a set to store possible LCS let s = new Set(); // 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 let 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 (let str of tmp.values()) 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]) { let 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 (let item of tmp.values()) s.add(item) } } return s; } /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ function LCS(X,Y,m,n) { // Build L[m+1][n+1] in bottom up fashion for (let i = 0; i <= m; i++) { for (let 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 let X = "AGTGATG" ; let Y = "GTTAG" ; let m = X.length; let n = Y.length; document.write( "LCS length is " + LCS(X, Y, m, n)+ "<br>" ); let s = findLCS(X, Y, m, n); for (let str of s.values()) document.write(str+ "<br>" ); // This code is contributed by rag2127 </script> |
输出：
LCS length is 4GTAGGTTG
参考资料： 维基百科——阅读所有LCS 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
