Chittagong University of Enginnering and Technology, Bangladesh

ACMBEGINNER

 

Home\ Tutorial \ LCS

 Version 2.0

 Longest Common Subsequence    

 

Background 

Given two sequence X and Y, we say that a sequence z is a common subsequence of C and Y if Z is a subsequence of both X and Y.

longest common subsequence (LCS) is just the longest "common subsequence" of two sequences.

A brute force approach of finding LCS such as enumerating all subsequences and finding the longest common one takes too much time. However, We have a Dynamic Programming solution for LCS problem. For details, you can refer to Introduction to Algorithm, By by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest second edition chapter 15 (Dynamic Programming), I will write the algorithm first and then code of this, written in C++, ready to use.

The  algorithm :

LCS_LENGTH(X,Y)
Input two sequence X<x1,x2,x3,....xm> and Y<y1,y2,y3.....yn>. It stores the C[i,j] values in the table C[0...m,0...n] whose entries are computed in row major order. It also maintain the table b[1...m,1...n] to simplify construction of an optimal solution. 

  1. m <- length[X]

  2. n <- length[Y]

  3. for i <- 1 to m

  4.              do c[I,0] <- 0

  5. for j <- 0 to n

  6.              do c[0,j] <- 0

  7. for i <- 1 to m

  8.              for j <- 1 to n

  9.                         do if xi = y j

  10.                              then c[i,j] <- c[i -1,j-1]+1

  11.                                      b[i,j] <- 1

  12.                              else if  c[i 1,j] >= c[i,j-1]

  13.                                     then c[i,j] <- c[i 1,j]

  14.                                             b[i,j] <- 2

  15.                                     else c[i,j] <- c[i,j-1]

  16.  return c and b

PRINT_ LCS(b,X,i,j)
This algorithm print the LCS

  1. if i = 0 or j = 0

  2.         then return

  3. if b[i,j] = 1

  4.         then PRINT_LCS(b,X,i-1,j-1)

  5. else if b[i,j] = 2

  6.         then PRINT_LCS(b,X,i-1,j)

  7. else PRINT_LCS(b,X,i,j-1)

Question: Can you list out ALL possible LCS?
Answer: Modify printLCS(), details will be available later.

 

/* LCS1.cpp

   Implementation of general LCS algorithm. The following code find an LCS of characters.

  

   Compiled : CYGNU & Microsoft Visual C++ 6.0

 

   Copyright 2003 by M H Rasel and CUET Old Sailor; all rights reserved.

 

   Permission is granted for use in non-commerical applications

   provided this copyright notice remains intact and unchanged.

*/

 

#include<stdio.h>

#include<string.h>

 

#define MAX 100 // size of each sequence

 

char str1[MAX],str2[MAX]; // the sequences

 

/* *********************************************** */

/*    This function print the LCS to the screen    */

/*     Input : A table generated by the LCS_LNT    */

/*            and the length ot the sequences      */

/*     Output: None                                */

/* *********************************************** */

void p_lcs(int b[MAX][MAX],int i,int j)

{

   if ( (i == 0) || ( j == 0) )      return ;

   if( b[i][j] == 1 )

   {   p_lcs(b,i-1,j-1);

      printf("%3c",str1[i-1]);

   }

   else if( b[i][j] == 2)       p_lcs(b,i-1,j);

   else                p_lcs(b,i,j-1);

}

 

/* ********************************************* */

/*    This function calculate the LCS length     */

/*    Input : Tow Sequence and an bool I. If     */

/*             I is FALSE(0) then the function   */

/*             do not print the LCS and if       */

/*             TRUE(1) then print using the      */

/*             above p_lcs function              */

/*    Output: None                               */

/* ********************************************* */

void LCS_LNT(bool I)

{

   int c[MAX][MAX]={0},b[MAX][MAX]={0},l1,l2;

   l1 = strlen(str1)+1;

   l2 = strlen(str2)+1;

 

   register int i,j;

   for(i=1;i<l1;i++)

   {   for(j=1;j<l2;j++)

       {  if( str1[i-1] == str2[j-1] )

          {   c[i][j] = c[i-1][j-1] + 1;

             b[i][j] = 1;

          }

          else if(c[i-1][j] >= c[i][j-1])

          {   c[i][j] = c[i-1][j];

             b[i][j] = 2;

          }

          else   c[i][j] = c[i][j-1];

       }

   }

   printf("%d\n",c[l1-1][l2-1]);

   if(I)     p_lcs(b,l1-1,l2-1);

}

 

/* a sample main function */

main(void)

{

   while(1)

   {

      if(!(gets(str1)))          return 0;

      if(!(gets(str2)))          return 0;

      LCS_LNT(1);

   }

}

/* *********************************************************************************** */

 

/* LCS2.cpp

   Implementation of general LCS algorithm. The following code find an LCS of words.

  

   Compiled : CYGNU & Microsoft Visual C++ 6.0

 

   Copyright 2003 by M H Rasel and CUET Old Sailor; all rights reserved.

 

   Permission is granted for use in non-commerical applications

   provided this copyright notice remains intact and unchanged.

*/

 

#include<stdio.h>

#include<string.h>

 

#define MAX 105

 

char str1[MAX][50],str2[MAX][50],lcs[MAX][50];

int lcswl;

 

/* *********************************************** */

/*    This function print the LCS to the screen    */

/*     Input : A table generated by the LCS_LNT    */

/*        and the length ot the sequences          */

/*    Output: None                                 */

/* *********************************************** */

void p_lcs(int b[MAX][MAX],int i,int j)

{

   if ( (i == 0) || ( j == 0) )      return ;

   if( b[i][j] == 1 )

   {

      p_lcs(b,i-1,j-1);

      strcpy(lcs[lcswl++],str1[i-1]);

   }

   else if( b[i][j] == 2)           p_lcs(b,i-1,j);

   else                   p_lcs(b,i,j-1);

}

 

/* ********************************************* */

/*    This function calculate the LCS length     */

/*    Input : Tow Sequence and an bool I. If     */

/*            I is FALSE(0) then the function    */

/*            do not print the LCS and if        */

/*            TRUE(1) then print using the       */

/*            above p_lcs function               */

/*    Output: None                               */

/* ********************************************* */

void LCS_LNT(int l1, int l2,bool I)

{

   int c[MAX][MAX]={0},b[MAX][MAX]={0};

   register int i,j;

   for(i=1;i<l1;i++)

   {   for(j=1;j<l2;j++)

       {  if( !(strcmp(str1[i-1],str2[j-1])))

          {   c[i][j] = c[i-1][j-1] + 1;

             b[i][j] = 1;

          }

          else if(c[i-1][j] >= c[i][j-1])

          {   c[i][j] = c[i-1][j];

             b[i][j] = 2;

          }

          else   c[i][j] = c[i][j-1];

       }

   }

   if(I)

   {

       lcswl = 0;

      p_lcs(b,l1-1,l2-1);

       j = c[l1-1][l2-1];

      printf("%s",lcs[0]);

       for(i = 1; i< j ;i++)        printf(" %s",lcs[i]);

      putchar('\n');

   }

}

 

/* Sample main function */

main(void)

{

   char word[50];

   int i=0,j=0,l1,l2,ln;

   while(scanf("%s",word)!=EOF)

   {

       ln = strlen(word);

      if(ln==1)

          if(word[0] == '#')

          {

             if(i==0)

             {

                 i = 1;

                 l1 =j;

                 j = 0;

                 continue;

             }

             else

             {

                 l2 = j;

                 j = i = 0;

                 test(l1+1,l2+1,1);

                 continue;

             }

          }

      if(i==0)   strcpy(str1[j++],word);

       else      strcpy(str2[j++],word);

   }

   return 0;

}

 

 

Copyright 2003 M H Rasel
[
Webmaster]
Last modified

1