Печат на най -дългата често срещана последователност | Комплект 2 (отпечатване на всички)
Като се има предвид две последователности, отпечатват всички най -дълги последствия, присъстващи и в двете.
Примери:
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
Обсъждахме проблема с най -дългата честота (LCS) тук . Функцията, обсъдена там, беше главно за намиране на дължината на LCS. Обсъждахме и как да отпечатаме най -дългата последователност тук . Но тъй като LCS за два струни не е уникален в тази публикация, ние ще разпечатаме всички възможни решения на проблема с LCS.
Следва подробен алгоритъм за отпечатване на всички LC.
Конструираме l [m+1] [n+1] таблица, както е обсъдено в предишен Публикувайте и преминете 2D масива, започващ от L [M] [n]. За текущата клетка l [i] [j] в матрицата
а) Ако последните знаци на x и y са еднакви (т.е. x [i-1] == y [j-1]), символът трябва да присъства във всички LCs на подреда x [0 ... I-1] и y [0..J-1]. Ние просто се повтаряме за L [I-1] [J-1] в матрицата и добавяме токов характер на всички LC, възможни на подстриране x [0 ... I-2] и y [0..J-2].
б) Ако последните знаци на x и y не са еднакви (т.е. x [i-1]! = y [j-1]), тогава LC могат да бъдат конструирани от горната страна на матрицата (т.е. l [i-1] [j]) или от лявата страна на матрицата (т.е. l [i] [j-1]) в зависимост от това, от което стойността е по-голяма. Ако и двете стойности са равни (т.е. l [i-1] [j] == l [i] [j-1]), тогава тя ще бъде конструирана от двете страни на матрицата. Така че въз основа на стойности при l [i-1] [j] и l [i] [j-1] вървим в посока с по-голяма стойност или отиваме в двете посоки, ако стойностите са равни.
По -долу е рекурсивно прилагане на горната идея -
/* 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
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-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 ( 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 ) + '
' ); let s = findLCS ( X Y m n ); for ( let str of s . values ()) document . write ( str + '
' ); // This code is contributed by rag2127 < /script>
Резултат:
LCS length is 4 GTAG GTTG
Сложност на времето: Това ще бъде експоненциално, защото използваме рекурсия, за да намерим всички възможни LC.
Космическа сложност: O (n*n)
Референции: WikiBooks - Четене на всички LCSS
