IMPRESSION DE LA SOUS-SÉQUENCE COMMUNE LA PLUS LONGUE | ENSEMBLE 2 (TOUT IMPRIMER)

Étant donné deux séquences, imprimez toutes les sous-séquences les plus longues présentes dans les deux.
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

Nous avons discuté du problème de la plus longue sous-séquence commune (LCS) ici . La fonction discutée là-bas était principalement de trouver la longueur du LCS. Nous avons également discuté de la façon d'imprimer la sous-séquence la plus longue ici . Mais comme le LCS pour deux chaînes n'est pas unique, dans cet article, nous imprimerons toutes les solutions possibles au problème du LCS.
Voici un algorithme détaillé pour imprimer tous les LCS.
Nous construisons la table L[m+1][n+1] comme indiqué dans le précédent publier et parcourir le tableau 2D à partir de L[m][n]. Pour la cellule actuelle L[i][j] dans la matrice
a) Si les derniers caractères de X et Y sont identiques (c'est-à-dire X[i-1] == Y[j-1]), alors le caractère doit être présent dans tous les LCS de la sous-chaîne X[0...i-1] et Y[0..j-1]. Nous récurons simplement L[i-1][j-1] dans la matrice et ajoutons le caractère actuel à tous les LCS possibles de la sous-chaîne X[0...i-2] et Y[0..j-2].
b) Si les derniers caractères de X et Y ne sont pas identiques (c'est-à-dire X[i-1] != Y[j-1]), alors LCS peut être construit à partir de l'un ou l'autre côté supérieur de la matrice (c'est-à-dire L[i-1][j]) ou à partir du côté gauche de la matrice (c'est-à-dire L[i][j-1]) selon la valeur la plus grande. Si les deux valeurs sont égales (c'est-à-dire L[i-1][j] == L[i][j-1]), alors elle sera construite des deux côtés de la matrice. Ainsi, sur la base des valeurs en L[i-1][j] et L[i][j-1], nous allons dans le sens d'une valeur plus élevée ou allons dans les deux sens si les valeurs sont égales.
Vous trouverez ci-dessous l’implémentation récursive de l’idée ci-dessus –

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>

Sortir:

LCS length is 4 GTAG GTTG

Complexité temporelle : Ce sera exponentiel car nous utilisons la récursion pour trouver tous les LCS possibles.

Complexité spatiale : O(n*n)
Références : Wikibooks - Lecture de tous les LCS

TechCodeview

Impression de la sous-séquence commune la plus longue | Ensemble 2 (Tout imprimer)