Print all longest common sub | Javascript 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
let MAX = 100 ; let lcslen = 0 ; let dp = new Array ( MAX ) ; function lcs ( str1 , str2 , len1 , len2 , i , j ) { let ret = dp [ i ] [ j ] ; if ( i == len1 j == len2 ) return ret = 0 ; if ( ret != - 1 ) return ret ; ret = 0 ; 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 printAll ( str1 , str2 , len1 , len2 , data , indx1 , indx2 , currlcs ) { if ( currlcs == lcslen ) { data [ currlcs ] = null ; document . write ( data . join ( " " ) + " " ) ; return ; } if ( indx1 == len1 indx2 == len2 ) return ; for ( let ch = ' ' . charCodeAt ( 0 ) ; ch <= ' ' . charCodeAt ( 0 ) ; ch ++ ) { let done = false ; for ( let i = indx1 ; i < len1 ; i ++ ) { if ( ch == str1 [ i ] . charCodeAt ( 0 ) ) { for ( let j = indx2 ; j < len2 ; j ++ ) { 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 ( done ) break ; } } } function prinlAllLCSSorted ( str1 , str2 ) { let len1 = str1 . length , len2 = str2 . length ; 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 ) ; let data = new Array ( MAX ) ; printAll ( str1 , str2 , len1 , len2 , data , 0 , 0 , 0 ) ; } let str1 = " " , str2 = " " ; prinlAllLCSSorted ( str1 , str2 ) ;