masum1004066's blog

By masum1004066, 8 years ago, In English

How can i print all different LONGEST COMMON SUB-SEQUENCE(LCS) of two different string.

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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]) 
           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   Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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<<way[k];
              cout<<endl;
              return;
           };
         //COUT ANSWER:END
           if (a[i]==b[j]){     // then answer is a[i];
              way[s+1]=a[i]; 
              dfs(i-1,j-1,s+1);
           } else {    
             if (ans[i-1][j]<ans[i][j-1])
                 dfs(i,j-1);
             else 
                if (ans[i-1][j]>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 :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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].

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no this doesn't work it adds a char to the answer even it's not in the solution or not

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

After the lasha explain you can try this problem TRIP

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://ceoi.inf.elte.hu/probarch/03/trip-solution.pdf

This 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.

»
6 days ago, # |
  Vote: I like it -8 Vote: I do not like it

string LCSbottomup( string str1, string str2) { int n = str1.size(); int k = str2.size(); vector<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; }