Longest common subsequence (LCS)

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.

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)

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)

All Code:
#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);
}
int main(void)
{
 while(1)
 {
 if(!(gets(str1))) return 0;
 if(!(gets(str2))) return 0;
 LCS_LNT(1);
 }
}

Another way:

#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');
 }
}
int 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;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s