### masum1004066's blog

By masum1004066, 8 years ago, How can i print all different LONGEST COMMON SUB-SEQUENCE(LCS) of two different string. Comments (10)
 » 8 years ago, # | ← Rev. 2 →   need NxM matrix,where ans[i][j] is answer from first string with length i and second string with length j,then if a[i]=b[j]; ans[i][j]=ans[i-1][j-1]+1; else ans[i][j]=max(ans[i-1,j],ans[i,j-1]); and length of LCS will be in ans[n][m]; and for finding all different LCS go to from ans[n,m] back:  i=n; j=m; while (i>0 && j>0) if (a[i]==b[j]){ way[++s]=a[i]; i--; J--; } else { if (g[i-1][j]g[i][j-1]) i--; else /*IS 2 WAY TO CONTINUE,AND YOU CAN USE way MATRIX*/ }; sorry for my poor english.
•  » » 8 years ago, # ^ | ← Rev. 4 →   thanks for reply. if string A="abcd" and string B="acbd" .Here,LCS will be abd and acd both. If i want to print both of them,how can i do that? By the above process u described, i can't print both of them. PLEASE HELP.
•  » » » you can use dfs(i,j,s) where i and j is indexes of Matrix and s is length of answer way: void dfs(int i,int j,int s){ //COUT ANSWER:BEGIN if (i<=0 || j<=0){ for (int k=1;k<=s;k++) cout<ans[i][j-1]) dfs(i-1,j,s); else { // is 2 way to continue dfs(i-1,j,s); dfs(i,j-1,s); }; }; }; and in main program when you have got ANS matrix then you can go to dfs(n,m,1); and this dfs go output both of them.sorry for my poor english again :)
•  » » you can do this: string sol = ""; for(int i = 0; i < l1; i++) { for(int j = 0; j < l2; j++) { if(s1[i] == s2[j]) { M[i][j] = M[i-1][j-1] + 1; sol += s1[i]; } else M[i][j] = max(M[i-1][j], M[i][j-1]); } } M[i][j] is the matrix, sol is the subsequence and l1 and l2 are the length of both strings s1 and s2. Also the length of the subsequence is M[l1-1][l2-1].
•  » » » no this doesn't work it adds a char to the answer even it's not in the solution or not
 » After the lasha explain you can try this problem TRIP
 » can anybody please give the recursive soln of printing all LCS ?? i did LCS recursively,,i can print LCS any 1 bt can't get any way how to print all LCS recursively
•  » »
 » http://ceoi.inf.elte.hu/probarch/03/trip-solution.pdfThis link explains how we can reduce repeated calls when d[i-1][j] equals d[i][j-1] , given that we know an upper bound on the total number of distinct lcs.
 » string LCSbottomup( string str1, string str2) { int n = str1.size(); int k = str2.size(); vector dp(n + 1, vector (k + 1, 0)); string output = ""; int maxx = 0; for( int i = 1 ; i <= n; i++) { for( int j = 1 ; j <= k; j++) { if(str2[j — 1] == str1[i — 1]) { dp[i][j] = 1 + dp[i — 1][j — 1]; if( dp[i][j] > maxx) { output += str2[j-1]; maxx = dp[i][j]; } } else dp[i][j] = max(dp[i — 1][j], dp[i][j — 1]); } } return output; }