Având în vedere două secvențe tipăriți toate cele mai lungi subsecvențe prezente în ambele.
Exemple:
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
Am discutat despre cea mai lungă problemă de subsecvență comună (LCS) Aici . Funcția discutată a fost în principal pentru a găsi lungimea LC. De asemenea, am discutat despre cum să imprimați cea mai lungă subsecvență Aici . Dar, deoarece LCS pentru două șiruri nu este unic în această postare, vom tipări toate soluțiile posibile la problema LCS.
Urmează algoritmul detaliat pentru a imprima toate LC -urile.
Construim tabelul L [m+1] [n+1] așa cum este discutat în anterior Postează și traversează tabloul 2D pornind de la l [m] [n]. Pentru celula actuală l [i] [j] în matrice
a) Dacă ultimele caractere ale lui X și Y sunt aceleași (adică x [i-1] == y [j-1]), atunci personajul trebuie să fie prezent în toate LC-urile de substrat x [0 ... i-1] și y [0..J-1]. Pur și simplu ne reaplicăm pentru l [i-1] [j-1] în matrice și adăugăm caracterul curent la toate LC-urile posibile de substrat x [0 ... i-2] și y [0..J-2].
b) Dacă ultimele caractere ale lui X și Y nu sunt aceleași (adică X [I-1]! = Y [J-1]), atunci LC-urile pot fi construite din oricare dintre partea superioară a matricei (adică L [I-1] [J]) sau din partea stângă a matricei (adică L [i] [J-1]), în funcție de care valoare este mai mare. Dacă ambele valori sunt egale (adică l [i-1] [j] == l [i] [j-1]), atunci va fi construită din ambele părți ale matricei. Deci, pe baza valorilor la l [i-1] [j] și l [i] [j-1] mergem în direcția unei valori mai mari sau mergem în ambele direcții dacă valorile sunt egale.
Mai jos este implementarea recursivă a ideii de mai sus -
/* Dynamic Programming implementation of LCS problem */ #include
/* 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
# 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
// 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-1n] == L[mn-1] // Note s will be empty if L[m-1n] != L[mn-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+1n+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
<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(XYmn) { // 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(XYmn) { // 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)+'
'); let s = findLCS(X Y m n); for (let str of s.values()) document.write(str+'
'); // This code is contributed by rag2127 </script>
Ieșire:
LCS length is 4 GTAG GTTG
Complexitate a timpului: Va fi exponențial, deoarece folosim Recursion pentru a găsi toate LC -urile posibile.
Complexitate spațială: O (n*n)
Referințe: Wikibooks - Citiți toate LCS -urile