Vytiskněte všechny nejdelší společné podsekvence v lexikografickém pořadí
Zkuste to na GfG Practice 
#practiceLinkDiv { display: none !important; }
Výstup
#practiceLinkDiv { display: none !important; } Dostanete dva řetězce, jejichž úkolem je vytisknout všechny nejdelší společné podsekvence v lexikografickém pořadí.
Příklady:
Input : str1 = 'abcabcaa' str2 = 'acbacba' Output: ababa abaca abcba acaba acaca acbaa acbcaRecommended Practice Vytiskněte všechny sekvence LCS Zkuste to!
Tento problém je rozšířením nejdelší společná podsekvence . Nejprve zjistíme délku LCS a uložíme všechny LCS do 2D tabulky pomocí Memoization (nebo Dynamic Programming). Poté hledáme všechny znaky od 'a' do 'z' (pro výstup seřazeného pořadí) v obou řetězcích. Pokud je znak nalezen v obou řetězcích a aktuální pozice znaku vedou k LCS, prohledáváme rekurzivně všechny výskyty s aktuální délkou LCS plus 1.
Níže je uvedena implementace algoritmu.
C++ // C++ program to find all LCS of two strings in // sorted order. #include #define MAX 100 using namespace std ; // length of lcs int lcslen = 0 ; // dp matrix to store result of sub calls for lcs int dp [ MAX ][ MAX ]; // A memoization based function that returns LCS of // str1[i..len1-1] and str2[j..len2-1] int lcs ( string str1 string str2 int len1 int len2 int i int j ) { int & ret = dp [ i ][ j ]; // base condition if ( i == len1 || j == len2 ) return ret = 0 ; // if lcs has been computed if ( ret != -1 ) return ret ; ret = 0 ; // if characters are same return previous + 1 else // max of two sequences after removing i'th and j'th // char one by one if ( str1 [ i ] == str2 [ j ]) ret = 1 + lcs ( str1 str2 len1 len2 i + 1 j + 1 ); else ret = max ( lcs ( str1 str2 len1 len2 i + 1 j ) lcs ( str1 str2 len1 len2 i j + 1 )); return ret ; } // Function to print all routes common sub-sequences of // length lcslen void printAll ( string str1 string str2 int len1 int len2 char data [] int indx1 int indx2 int currlcs ) { // if currlcs is equal to lcslen then print it if ( currlcs == lcslen ) { data [ currlcs ] = ' ' ; puts ( data ); return ; } // if we are done with all the characters of both string if ( indx1 == len1 || indx2 == len2 ) return ; // here we have to print all sub-sequences lexicographically // that's why we start from 'a'to'z' if this character is // present in both of them then append it in data[] and same // remaining part for ( char ch = 'a' ; ch <= 'z' ; ch ++ ) { // done is a flag to tell that we have printed all the // subsequences corresponding to current character bool done = false ; for ( int i = indx1 ; i < len1 ; i ++ ) { // if character ch is present in str1 then check if // it is present in str2 if ( ch == str1 [ i ]) { for ( int j = indx2 ; j < len2 ; j ++ ) { // if ch is present in both of them and // remaining length is equal to remaining // lcs length then add ch in sub-sequence if ( ch == str2 [ j ] && dp [ i ][ j ] == lcslen - currlcs ) { data [ currlcs ] = ch ; printAll ( str1 str2 len1 len2 data i + 1 j + 1 currlcs + 1 ); done = true ; break ; } } } // If we found LCS beginning with current character. if ( done ) break ; } } } // This function prints all LCS of str1 and str2 // in lexicographic order. void prinlAllLCSSorted ( string str1 string str2 ) { // Find lengths of both strings int len1 = str1 . length () len2 = str2 . length (); // Find length of LCS memset ( dp -1 sizeof ( dp )); lcslen = lcs ( str1 str2 len1 len2 0 0 ); // Print all LCS using recursive backtracking // data[] is used to store individual LCS. char data [ MAX ]; printAll ( str1 str2 len1 len2 data 0 0 0 ); } // Driver program to run the case int main () { string str1 = 'abcabcaa' str2 = 'acbacba' ; prinlAllLCSSorted ( str1 str2 ); return 0 ; }
Java // Java program to find all LCS of two strings in // sorted order. import java.io.* ; class GFG { static int MAX = 100 ; // length of lcs static int lcslen = 0 ; // dp matrix to store result of sub calls for lcs static int [][] dp = new int [ MAX ][ MAX ] ; // A memoization based function that returns LCS of // str1[i..len1-1] and str2[j..len2-1] static int lcs ( String str1 String str2 int len1 int len2 int i int j ) { int ret = dp [ i ][ j ] ; // base condition if ( i == len1 || j == len2 ) return ret = 0 ; // if lcs has been computed if ( ret != - 1 ) return ret ; ret = 0 ; // if characters are same return previous + 1 else // max of two sequences after removing i'th and j'th // char one by one if ( str1 . charAt ( i ) == str2 . charAt ( j )) ret = 1 + lcs ( str1 str2 len1 len2 i + 1 j + 1 ); else ret = Math . max ( lcs ( str1 str2 len1 len2 i + 1 j ) lcs ( str1 str2 len1 len2 i j + 1 )); return dp [ i ][ j ]= ret ; } // Function to print all routes common sub-sequences of // length lcslen static void printAll ( String str1 String str2 int len1 int len2 char [] data int indx1 int indx2 int currlcs ) { // if currlcs is equal to lcslen then print it if ( currlcs == lcslen ) { data [ currlcs ] = ' ' ; System . out . println ( new String ( data )); return ; } // if we are done with all the characters of both string if ( indx1 == len1 || indx2 == len2 ) return ; // here we have to print all sub-sequences lexicographically // that's why we start from 'a'to'z' if this character is // present in both of them then append it in data[] and same // remaining part for ( char ch = 'a' ; ch <= 'z' ; ch ++ ) { // done is a flag to tell that we have printed all the // subsequences corresponding to current character boolean done = false ; for ( int i = indx1 ; i < len1 ; i ++ ) { // if character ch is present in str1 then check if // it is present in str2 if ( ch == str1 . charAt ( i )) { for ( int j = indx2 ; j < len2 ; j ++ ) { // if ch is present in both of them and // remaining length is equal to remaining // lcs length then add ch in sub-sequence if ( ch == str2 . charAt ( j ) && dp [ i ][ j ] == lcslen - currlcs ) { data [ currlcs ] = ch ; printAll ( str1 str2 len1 len2 data i + 1 j + 1 currlcs + 1 ); done = true ; break ; } } } // If we found LCS beginning with current character. if ( done ) break ; } } } // This function prints all LCS of str1 and str2 // in lexicographic order. static void prinlAllLCSSorted ( String str1 String str2 ) { // Find lengths of both strings int len1 = str1 . length () len2 = str2 . length (); // Find length of LCS for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ][ j ] = - 1 ; } } lcslen = lcs ( str1 str2 len1 len2 0 0 ); // Print all LCS using recursive backtracking // data[] is used to store individual LCS. char [] data = new char [ MAX ] ; printAll ( str1 str2 len1 len2 data 0 0 0 ); } // Driver code public static void main ( String [] args ) { String str1 = 'abcabcaa' str2 = 'acbacba' ; prinlAllLCSSorted ( str1 str2 ); } } // This code is contributed by divyesh072019
Python3 # Python3 program to find all LCS of two strings in # sorted order. MAX = 100 lcslen = 0 # dp matrix to store result of sub calls for lcs dp = [[ - 1 for i in range ( MAX )] for i in range ( MAX )] # A memoization based function that returns LCS of # str1[i..len1-1] and str2[j..len2-1] def lcs ( str1 str2 len1 len2 i j ): # base condition if ( i == len1 or j == len2 ): dp [ i ][ j ] = 0 return dp [ i ][ j ] # if lcs has been computed if ( dp [ i ][ j ] != - 1 ): return dp [ i ][ j ] ret = 0 # if characters are same return previous + 1 else # max of two sequences after removing i'th and j'th # char one by one if ( str1 [ i ] == str2 [ j ]): ret = 1 + lcs ( str1 str2 len1 len2 i + 1 j + 1 ) else : ret = max ( lcs ( str1 str2 len1 len2 i + 1 j ) lcs ( str1 str2 len1 len2 i j + 1 )) dp [ i ][ j ] = ret return ret # Function to print all routes common sub-sequences of # length lcslen def printAll ( str1 str2 len1 len2 data indx1 indx2 currlcs ): # if currlcs is equal to lcslen then print if ( currlcs == lcslen ): print ( '' . join ( data [: currlcs ])) return # if we are done with all the characters of both string if ( indx1 == len1 or indx2 == len2 ): return # here we have to print all sub-sequences lexicographically # that's why we start from 'a'to'z' if this character is # present in both of them then append it in data[] and same # remaining part for ch in range ( ord ( 'a' ) ord ( 'z' ) + 1 ): # done is a flag to tell that we have printed all the # subsequences corresponding to current character done = False for i in range ( indx1 len1 ): # if character ch is present in str1 then check if # it is present in str2 if ( chr ( ch ) == str1 [ i ]): for j in range ( indx2 len2 ): # if ch is present in both of them and # remaining length is equal to remaining # lcs length then add ch in sub-sequence if ( chr ( ch ) == str2 [ j ] and dp [ i ][ j ] == lcslen - currlcs ): data [ currlcs ] = chr ( ch ) printAll ( str1 str2 len1 len2 data i + 1 j + 1 currlcs + 1 ) done = True break # If we found LCS beginning with current character. if ( done ): break # This function prints all LCS of str1 and str2 # in lexicographic order. def prinlAllLCSSorted ( str1 str2 ): global lcslen # Find lengths of both strings len1 len2 = len ( str1 ) len ( str2 ) lcslen = lcs ( str1 str2 len1 len2 0 0 ) # Print all LCS using recursive backtracking # data[] is used to store individual LCS. data = [ 'a' for i in range ( MAX )] printAll ( str1 str2 len1 len2 data 0 0 0 ) # Driver program to run the case if __name__ == '__main__' : str1 = 'abcabcaa' str2 = 'acbacba' prinlAllLCSSorted ( str1 str2 ) # This code is contributed by mohit kumar 29
C# // C# program to find all LCS of two strings in // sorted order. using System ; class GFG { static int MAX = 100 ; // length of lcs static int lcslen = 0 ; // dp matrix to store result of sub calls for lcs static int [] dp = new int [ MAX MAX ]; // A memoization based function that returns LCS of // str1[i..len1-1] and str2[j..len2-1] static int lcs ( string str1 string str2 int len1 int len2 int i int j ) { int ret = dp [ i j ]; // base condition if ( i == len1 || j == len2 ) return ret = 0 ; // if lcs has been computed if ( ret != - 1 ) return ret ; ret = 0 ; // if characters are same return previous + 1 else // max of two sequences after removing i'th and j'th // char one by one if ( str1 [ i ] == str2 [ j ]) ret = 1 + lcs ( str1 str2 len1 len2 i + 1 j + 1 ); else ret = Math . Max ( lcs ( str1 str2 len1 len2 i + 1 j ) lcs ( str1 str2 len1 len2 i j + 1 )); return ret ; } // Function to print all routes common sub-sequences of // length lcslen static void printAll ( string str1 string str2 int len1 int len2 char [] data int indx1 int indx2 int currlcs ) { // if currlcs is equal to lcslen then print it if ( currlcs == lcslen ) { data [ currlcs ] = ' ' ; Console . WriteLine ( new string ( data )); return ; } // if we are done with all the characters of both string if ( indx1 == len1 || indx2 == len2 ) return ; // here we have to print all sub-sequences lexicographically // that's why we start from 'a'to'z' if this character is // present in both of them then append it in data[] and same // remaining part for ( char ch = 'a' ; ch <= 'z' ; ch ++ ) { // done is a flag to tell that we have printed all the // subsequences corresponding to current character bool done = false ; for ( int i = indx1 ; i < len1 ; i ++ ) { // if character ch is present in str1 then check if // it is present in str2 if ( ch == str1 [ i ]) { for ( int j = indx2 ; j < len2 ; j ++ ) { // if ch is present in both of them and // remaining length is equal to remaining // lcs length then add ch in sub-sequence if ( ch == str2 [ j ] && lcs ( str1 str2 len1 len2 i j ) == lcslen - currlcs ) { data [ currlcs ] = ch ; printAll ( str1 str2 len1 len2 data i + 1 j + 1 currlcs + 1 ); done = true ; break ; } } } // If we found LCS beginning with current character. if ( done ) break ; } } } // This function prints all LCS of str1 and str2 // in lexicographic order. static void prinlAllLCSSorted ( string str1 string str2 ) { // Find lengths of both strings int len1 = str1 . Length len2 = str2 . Length ; // Find length of LCS for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i j ] = - 1 ; } } lcslen = lcs ( str1 str2 len1 len2 0 0 ); // Print all LCS using recursive backtracking // data[] is used to store individual LCS. char [] data = new char [ MAX ]; printAll ( str1 str2 len1 len2 data 0 0 0 ); } // Driver code static void Main () { string str1 = 'abcabcaa' str2 = 'acbacba' ; prinlAllLCSSorted ( str1 str2 ); } } // This code is contributed by divyeshrabadiya07
JavaScript < script > // Javascript program to find all LCS of two strings in // sorted order. let MAX = 100 ; // length of lcs let lcslen = 0 ; // dp matrix to store result of sub calls for lcs let dp = new Array ( MAX ); // A memoization based function that returns LCS of // str1[i..len1-1] and str2[j..len2-1] function lcs ( str1 str2 len1 len2 i j ) { let ret = dp [ i ][ j ]; // base condition if ( i == len1 || j == len2 ) return ret = 0 ; // if lcs has been computed if ( ret != - 1 ) return ret ; ret = 0 ; // if characters are same return previous + 1 else // max of two sequences after removing i'th and j'th // char one by one if ( str1 [ i ] == str2 [ j ]) ret = 1 + lcs ( str1 str2 len1 len2 i + 1 j + 1 ); else ret = Math . max ( lcs ( str1 str2 len1 len2 i + 1 j ) lcs ( str1 str2 len1 len2 i j + 1 )); return ret ; } // Function to print all routes common sub-sequences of // length lcslen function printAll ( str1 str2 len1 len2 data indx1 indx2 currlcs ) { // if currlcs is equal to lcslen then print it if ( currlcs == lcslen ) { data [ currlcs ] = null ; document . write ( data . join ( '' ) + '
' ); return ; } // if we are done with all the characters of both string if ( indx1 == len1 || indx2 == len2 ) return ; // here we have to print all sub-sequences lexicographically // that's why we start from 'a'to'z' if this character is // present in both of them then append it in data[] and same // remaining part for ( let ch = 'a' . charCodeAt ( 0 ); ch <= 'z' . charCodeAt ( 0 ); ch ++ ) { // done is a flag to tell that we have printed all the // subsequences corresponding to current character let done = false ; for ( let i = indx1 ; i < len1 ; i ++ ) { // if character ch is present in str1 then check if // it is present in str2 if ( ch == str1 [ i ]. charCodeAt ( 0 )) { for ( let j = indx2 ; j < len2 ; j ++ ) { // if ch is present in both of them and // remaining length is equal to remaining // lcs length then add ch in sub-sequence if ( ch == str2 [ j ]. charCodeAt ( 0 ) && lcs ( str1 str2 len1 len2 i j ) == lcslen - currlcs ) { data [ currlcs ] = String . fromCharCode ( ch ); printAll ( str1 str2 len1 len2 data i + 1 j + 1 currlcs + 1 ); done = true ; break ; } } } // If we found LCS beginning with current character. if ( done ) break ; } } } // This function prints all LCS of str1 and str2 // in lexicographic order. function prinlAllLCSSorted ( str1 str2 ) { // Find lengths of both strings let len1 = str1 . length len2 = str2 . length ; // Find length of LCS for ( let i = 0 ; i < MAX ; i ++ ) { dp [ i ] = new Array ( MAX ); for ( let j = 0 ; j < MAX ; j ++ ) { dp [ i ][ j ] = - 1 ; } } lcslen = lcs ( str1 str2 len1 len2 0 0 ); // Print all LCS using recursive backtracking // data[] is used to store individual LCS. let data = new Array ( MAX ); printAll ( str1 str2 len1 len2 data 0 0 0 ); } // Driver code let str1 = 'abcabcaa' str2 = 'acbacba' ; prinlAllLCSSorted ( str1 str2 ); // This code is contributed by unknown2108 < /script>
Výstup
ababa abaca abcba acaba acaca acbaa acbca
Časová složitost: O(m*n*p) kde 'm' je délka pole znaků, 'n' je délka pole1 a 'p' je délka pole2.
Prostorová složitost: O(m*n) protože pro uložení výsledku používáme 2D matici velikosti m*n.
