Drukājiet visas garākās kopīgās apakšsecības leksikogrāfiskā secībā
Izmēģiniet to GfG Practice 
#practiceLinkDiv { display: none !important; }
Izvade
#practiceLinkDiv { display: none !important; } Jums tiek dotas divas virknes, kuru uzdevums ir izdrukāt visas garākās kopīgās apakšsecības leksikogrāfiskā secībā.
Piemēri:
Input : str1 = 'abcabcaa' str2 = 'acbacba' Output: ababa abaca abcba acaba acaca acbaa acbcaRecommended Practice Drukājiet visas LCS secības Izmēģiniet to!
Šī problēma ir paplašinājums garākā kopīgā secība . Vispirms mēs atrodam LCS garumu un visus LCS saglabājam 2D tabulā, izmantojot Memoization (vai dinamisko programmēšanu). Pēc tam abās virknēs mēs meklējam visas rakstzīmes no "a" līdz "z" (lai izvadītu sakārtotu secību). Ja rakstzīme ir atrasta abās virknēs un rakstzīmes pašreizējās pozīcijas noved pie LCS, mēs rekursīvi meklējam visus gadījumus ar pašreizējo LCS garumu plus 1.
Zemāk ir algoritma ieviešana.
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>
Izvade
ababa abaca abcba acaba acaca acbaa acbca
Laika sarežģītība: O(m*n*p) kur "m" ir rakstzīmju garums masīvs "n" ir masīva1 garums un "p" ir masīva2 garums.
Telpas sarežģītība: O(m*n) jo mēs izmantojam m*n izmēra 2D matricu rezultāta saglabāšanai.
