Print all longest common sub | Java program to find all LCS of two strings in sorted order . ; length of lcs ; dp matrix to store result of sub calls for lcs ; A memoization based function that returns LCS of str1 [ i . . len1 - 1 ] and str2 [ j . . len2 - 1 ] ; base condition ; if lcs has been computed ; if characters are same return previous + 1 else max of two sequences after removing i ' th ▁ and ▁ j ' th char one by one ; Function to print all routes common sub - sequences of length lcslen ; if currlcs is equal to lcslen then print it ; if we are done with all the characters of both string ; 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 ; done is a flag to tell that we have printed all the subsequences corresponding to current character ; if character ch is present in str1 then check if it is present in str2 ; if ch is present in both of them and remaining length is equal to remaining lcs length then add ch in sub - sequenece ; If we found LCS beginning with current character . ; This function prints all LCS of str1 and str2 in lexicographic order . ; Find lengths of both strings ; Find length of LCS ; Print all LCS using recursive backtracking data [ ] is used to store individual LCS . ; Driver code
class GFG { static int MAX = 100 ; static int lcslen = 0 ; static int [ ] [ ] dp = new int [ MAX ] [ MAX ] ; static int lcs ( String str1 , String str2 , int len1 , int len2 , int i , int j ) { int ret = dp [ i ] [ j ] ; if ( i == len1 j == len2 ) return ret = 0 ; if ( ret != - 1 ) return ret ; ret = 0 ; 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 ret ; } static void printAll ( String str1 , String str2 , int len1 , int len2 , char [ ] data , int indx1 , int indx2 , int currlcs ) { if ( currlcs == lcslen ) { data [ currlcs ] = ' \0' ; System . out . println ( new String ( data ) ) ; return ; } if ( indx1 == len1 indx2 == len2 ) return ; for ( char ch = ' a ' ; ch <= ' z ' ; ch ++ ) { boolean done = false ; for ( int i = indx1 ; i < len1 ; i ++ ) { if ( ch == str1 . charAt ( i ) ) { for ( int j = indx2 ; j < len2 ; j ++ ) { 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 ( done ) break ; } } } static void prinlAllLCSSorted ( String str1 , String str2 ) { int len1 = str1 . length ( ) , len2 = str2 . length ( ) ; 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 ) ; char [ ] data = new char [ MAX ] ; printAll ( str1 , str2 , len1 , len2 , data , 0 , 0 , 0 ) ; } public static void main ( String [ ] args ) { String str1 = " abcabcaa " , str2 = " acbacba " ; prinlAllLCSSorted ( str1 , str2 ) ; } }