Ņemot vērā divas sekvences, izdrukājot visas garākās secības, kas atrodas abās.
Piemēri:
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
Mēs esam apsprieduši garāko kopējo secību (LCS) problēmu šeit Apvidū Tur apspriestā funkcija galvenokārt bija paredzēta LC garuma atrašanai. Mēs arī esam apsprieduši, kā izdrukāt garāko secību šeit Apvidū Bet, tā kā LCS divām virknēm šajā amatā nav unikāla, mēs izdrukāsim visus iespējamos LCS problēmas risinājumus.
Tālāk ir detalizēts algoritms, lai izdrukātu visus LCS.
Mēs konstruējam l [m+1] [n+1] tabulu, kā aprakstīts iepriekšējs Pēc un šķērsojiet 2D masīvu, sākot no l [m] [n]. Pašreizējai šūnai l [i] [j] matricā
a) Ja x un y pēdējās rakstzīmes ir vienādas (t.i., x [i-1] == y [j-1]), tad rakstzīmei jābūt klāt visās apakšvirkšanas x [0 ... i-1] un y [0..j-1] LCS. Mēs vienkārši atkārtojam l [i-1] [J-1] matricā un pievienojam pašreizējo rakstzīmi visiem iespējamiem substring x [0 ... i-2] un y [0..j-2].
b) Ja x un y pēdējās rakstzīmes nav vienādas (t.i., x [i-1]! = y [J-1]), tad LC var veidot no abām matricas augšējām pusēm (t.i., l [i-1] [j]) vai no matricas kreisās puses (t.i., l [i] [j-1]), kas ir atkarīga no kura vērtība ir lielāka. Ja abas vērtības ir vienādas (t.i., l [i-1] [j] == l [i] [J-1]), tad tā tiks konstruēta no abām matricas pusēm. Tātad, pamatojoties uz vērtībām pie l [i-1] [j] un l [i] [J-1], mēs ejam lielākas vērtības virzienā vai ejam abos virzienos, ja vērtības ir vienādas.
Zemāk ir rekursīva iepriekšējās idejas ieviešana -
/* 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>
Izlaide:
LCS length is 4 GTAG GTTG
Laika sarežģītība: Tas būs eksponenciāls, jo mēs izmantojam rekursiju, lai atrastu visus iespējamos LC.
Kosmosa sarežģītība: O (n*n)
Atsauces: Wikibooks - visu LCSS lasīšana