masum1004066's blog

LCS
By masum1004066, 11 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

Comments Comments (8)
| Write comment?
»
11 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.

→ Reply
  • »
    »
    11 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.

    → Reply
    • »
      »
      »
      11 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 :)

      → Reply
  • »
    »
    11 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].

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   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

      → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

After the lasha explain you can try this problem TRIP

→ Reply
»
11 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

→ Reply