Longest Common Sub-Sequence

The longest common subsequence (LCS) problem is very popular in computer science. This problem can be solved by dynamic algorithm. We can define this problem to find the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Let A  = {1,3,4,6,8}
B = {7, 3,2,4,6,10,8}

LCS (A,B) = {3,4,6,8} , Length = 4;



Application:

• bioinformatics 
• revision control systems (the management of changes to documents, computer programs, large web sites, and other collections of information)

How can we solve this problem?
if we have two sequence of length n and m, the time complexity of the dynamic Program approach is O(nm).

Here, A = {4,7,6,5,9}
B = {2,3,4,6,5,9}
2 not belongs to A
3 also not belongs to A
4 belong to A  0+1 = 1
4!=7 = >  max (0,1) = 1,
.
.
.
finally we get length of LCS i.e. 4

we can print it as following:

#include<stdio.h>
#define max 100
#define MAX(a,b) a<b?b:a
int c[max][max];//table
int R[max],r=0;//R=result,r=lenth

void LCS(int *X,int *Y,int Lx,int Ly){
    int i,j;
 for(i=0;i<Lx;i++)
  c[i][0]=0;
 for(j=0;j<Ly;j++){
  c[0][j]=0;
  printf("%d\t",c[0][j]);
 }
    printf("\n");
    for(i=1;i<Lx;i++){
        printf("%d\t",c[i][0]);
        for(j=1;j<Ly;j++){
     if(X[i]==Y[j]){
      c[i][j] = c[i-1][j-1]+1;
      printf("%d\t",c[i][j]);
     }
     else{
      c[i][j]= MAX(c[i][j-1],c[i-1][j]);
      printf("%d\t",c[i][j]);
     }
  }
  printf("\n");
 }
}

int printLCS(int *X,int *Y,int i,int j){
   if(i==0||j==0)
    return 0;
   else if(X[i]==Y[j]){
    int m= printLCS(X,Y,i-1,j-1);
    printf("%d ",X[i]);
    R[r]=X[i];
    r++;
    return m;
   }
   else{
     if(c[i][j-1]>c[i-1][j])
   return printLCS(X,Y,i,j-1);
  else
   return printLCS(X,Y,i-1,j);
   }
   return 0;
}

int main(){
 int X[]={0,2,3,4,6,5,9};
 int Y[] = {0,4,7,6,5,9};
    /*freopen("LCSout.txt","w",stdout);*/

 LCS(X,Y,7,6);

    printf("\nPrint LCS: ");
 printLCS(X,Y,7,6);

 printf("\n\nResult: \n");
 printf("\tLenth: %d\n\t",r);
 for(int i=0;i<r;i++)
  printf("%d ",R[i]);
    printf("\n");
    return 0;
}