IMPRESSIÓ SUBSEQUÈNCIA COMUNA MÉS LLARGA | SET 2 (IMPRIMINT TOT)

Tenint en compte dues seqüències, imprimiu tota la subseqüència més llarga en totes dues.
Exemples:

  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

Hem discutit el problema de la subseqüència comuna més llarga (LCS) aquí . La funció discutida allà era principalment per trobar la longitud dels LC. També hem discutit com imprimir la subseqüència més llarga aquí . Però, com que LCS per a dues cadenes no és únic en aquesta publicació, imprimirem totes les solucions possibles al problema de LCS.
A continuació es mostra un algorisme detallat per imprimir tots els LC.
Construïm la taula L [m+1] [n+1] tal com es parla al previ Publicar i recórrer la matriu 2D a partir de L [m] [n]. Per a la cel·la actual L [i] [J] a la matriu
a) Si els últims caràcters de x i y són iguals (és a dir, x [i-1] == y [j-1]), el personatge ha d’estar present en tots els LC de la subcadena x [0 ... i-1] i y [0..J-1]. Simplement recursem per L [i-1] [J-1] a la matriu i afegim el caràcter actual a tots els LC possibles de la substring x [0 ... i-2] i y [0..J-2].
b) Si els últims caràcters de x i y no són els mateixos (és a dir, x [i-1]! = y [j-1]), els LC es poden construir des de qualsevol costat superior de la matriu (és a dir, l [i-1] [j]) o des del costat esquerre de la matriu (és a dir, l [i] [j-1]) depenent de quin valor és més gran. Si els dos valors són iguals (és a dir, l [i-1] [j] == l [i] [j-1]), es construirà a partir dels dos costats de la matriu. Així doncs, basant-nos en valors a L [i-1] [J] i L [i] [J-1] anem en direcció a un major valor o anem en ambdues direccions si els valors són iguals.
A continuació es mostra la implementació recursiva de la idea anterior:

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<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

// 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

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(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>

Sortida:

LCS length is 4 GTAG GTTG

Complexitat del temps: Serà exponencial perquè estem utilitzant recursió per trobar tots els LC possibles.

Complexitat espacial: O (n*n)
Referències: Wikibooks: llegint tots els LCSS

TechCodeview

Impressió Subsequència comuna més llarga | Set 2 (imprimint tot)