The following pseudocode is given for finding out the LCS. LCS-LENGTH (X, Y) m l

Question

The following pseudocode is given for finding out the LCS.

LCS-LENGTH (X, Y)

m length[X]
n length[Y]
for i 1 to m
     do c[i, 0] 0
for j 0 to n
     do c[0, j ] 0
for i 1 to m
      do for j 1 to n
           do if xi = yj
                    then c[i, j ] c[i-1, j-1] + 1
                             b[i, j ] “   ”
                    else if c[i-1, j ] c[i, j-1]
                           then c[i, j ] c[i- 1, j ]
                                    b[i, j ] “”
                            else c[i, j ] c[i, j-1]
                                   b[i, j ] “”
return c and b

Write a function to implement this. Define two matrices c and b, of type integer and character respectively. The code should take two strings X and Y as inputs and display the c matrix, b matrix as well as display the length of the LCS and the LCS. Test the function by calling it from main.

Explanation / Answer

<code>

#include<iostream>
using namespace std;
int main()
{
   string X,Y;
   cout << "Enter the two strings ";
   cin >> X >> Y;
   findLCS(X,Y);
   return 0;
}

void findLCS(string X, string Y)
{

   int m = X.length();
   int n = Y.length();
   char b[m+1][n+1];
   int c[m+1][n+1];

   for(int i = 0;i <= m;i++) {
       for(int j = 0; j <= n;j++) {
           if (i == 0 || j == 0){
               c[i][j] = 0;
           }
           else if(X[i-1] == Y[j-1]) {
               c[i][j] = c[i-1][j-1] + 1;
               b[i][j] = ' ';
           }else if(c[i-1][j] >= c[i][j-1]) {
               c[i][j] = c[i-1][j];
               b[i][j] = '|';
           }else {
               c[i][j] = c[i][j-1];
               b[i][j] = '-';
           }
       }
   }

   cout << "C Matrix is ";  
   for(int i = 0; i <= m;i++) {
       for(int j = 0; j <= n;j++) {
           cout << c[i][j] << " ";
       }
       cout << " ";
   }

   cout << " B Matrix is ";
   for(int i = 1; i <= m;i++) {
       for(int j = 1; j <= n;j++) {
           cout << b[i][j] << " ";
       }
       cout << " ";
   }

   int index = c[m][n];
   string str = "";
   int p = m;
   int q = n;
   while(p > 0 && q > 0) {
       if(X[p-1] == Y[q-1]) {
           str = X[p-1]+str;
           p--;q--;index--;
       }else if(c[p-1][q] > c[p][q-1]) {
               p--;
       }else {
           q--;
       }
   }
   cout << "LCS length is " << c[m][n] << " Result of LCS is " << str << endl;

}

</code>

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.