Tuesday 17 April 2012

Longest Common Subsequence(LCS) using Dynamic Pragramming and Finding one of the optimal solutions by Backtracking

/*
This finds the LCS by Dynamic Programming
*/

#include "iostream"
#include "string"
#include "vector"
using namespace std;
int main()
{
     string X,Y;
     int Xlen,Ylen;
     cin>>X;
     cin>>Y;
     Xlen = X.length();
     Ylen = Y.length();
     vector<vector<int>> table;
     table.resize(Xlen+1);
     for(int i=0;i<=Xlen;i++)
          table[i].resize(Ylen+1);
     for(int i=0; i<Xlen; i++)
          table[i][0] = 0;
     for(int i=0; i<Ylen; i++)
          table[0][i] = 0;
     int entry;
     for(int i=1; i<=Xlen; i++)
          for(int j=1; j<=Ylen; j++)
          {
               if(X[i-1] == Y[j-1])
              {
                    entry = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1];
                    entry = (table[i-1][j-1] + 1) > entry ?  (table[i-1][j-1] + 1) : entry;
                    table[i][j] = entry;
              }else
                    table[i][j] = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1];   
           }
     cout<<table[Xlen][Ylen]<<endl;

     //Back tracking to find one of the optimal solutions
     string LCS = "";
     for(int i=Xlen,j=Ylen;i>0 && j>0;)
     {
           if(X[i-1] == Y[j-1])
          {
                LCS.insert(LCS.begin(),X[i-1]);
                i--;
                j--;
          }
          else
          {
               if(table[i-1][j] > table[i][j-1])
                    i--;
               else
                    j--;
           }
      }
      cout<<"LCS string is "<<LCS;
      return 0;
}

No comments: