Блог пользователя masum1004066

Автор masum1004066, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 :)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

After the lasha explain you can try this problem TRIP

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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