Skip to main content

Longest Common Subsequence

Longest Common Subsequence



LCS\left(X_{i},Y_{j}\right) =
\begin{cases}
  \empty
& \mbox{ if }\ i = 0 \mbox{ or }  j = 0 \\
  \textrm{  } LCS\left(X_{i-1},Y_{j-1}\right) \frown x_{i}
& \mbox{ if } x_i = y_j \\
  \mbox{longest}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)
& \mbox{ if } x_i \ne y_j \\
\end{cases}


/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
  
   /* Following steps build L[m+1][n+1] in bottom up fashion. Note
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
  
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
  
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
    
   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
   return L[m][n];
}




// Following code is used to print LCS
   int index = L[m][n];
   // Create a character array to store the lcs string
   char lcs[index+1];
   lcs[index] = '\0'; // Set the terminating character
   // Start from the right-most-bottom-most corner and
   // one by one store characters in lcs[]
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      // If current character in X[] and Y are same, then
      // current character is part of LCS
      if (X[i-1] == Y[j-1])
      {
          lcs[index-1] = X[i-1]; // Put current character in result
          i--; j--; index--;     // reduce values of i, j and index
      }
      // If not same, then find the larger of two and
      // go in the direction of larger value
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }
   // Print the lcs
   cout << "LCS of " << X << " and " << Y << " is " << lcs;






Comments

Popular posts from this blog

ORACLE 9i practice solutions

Created by BCL easyConverter SDK 3 (HTML Version)

Hackerrank > SQL > Basic Select

Select
01-Select All
Given a City table, whose fields are described as +-------------+----------+ | Field       | Type     | +-------------+----------+ | ID          | int(11)  | | Name        | char(35) | | CountryCode | char(3)  | | District    | char(20) | | Population  | int(11)  | +-------------+----------+
write a query that will fetch all columns for every row in the table.

My Solution
SELECT*FROM city;
---------------------------------------------------------------------------------
02-Select by ID
Given a City table, whose fields are described as

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…