Longest Common Sub-sequence (LCS)

In computer science we use dynamic programming for solving complex problem. A good example for dynamic programming is longest common subsequence.   
Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure. Sometimes the subproblems are not independent, that is when sub-problems share subsubproblems. Dynamic programming algorithm solves every sub-problem just once and then saves its answer in a table.  


The longest common sub-sequence problem is a classic computer science problem, the basis of data comparison programs and has applications in bioinformatics.
The longest common sub-sequence (LCS) problem is to find the longest sub-sequence common to all sequences in a set of sequences (often just two).
LCS

First we look into only finding the length of LCS. We can easily construct an exponential time recursive algorithm to compute the length of the LCS. But using Dynamic Programming (DP) to compute the solution bottom up the same job can be done in O(mn) time where m and n are the lengths of the sub-sequences. Here is a C code to do so.

Implementing LCS in C:
 
#include<stdio.h>
#include<conio.h>
#include<string.h>
int i,j,m,n,a,c[20][20];
char x[15],y[15],b[20][20];
void print_lcs(int i,int j)
{
                if(i==0 || j==0)
                                return;
                if(b[i][j]=='c')
                {
                                print_lcs(i-1,j-1);
                                printf(" %c",x[i-1]);
                }
                else if(b[i][j]=='u')
                                print_lcs(i-1,j);
                else
                                print_lcs(i,j-1);
}
void lcs_length(void)
{
                m=strlen(x);
                n=strlen(y);
                for(i=0;i<=m;i++)
                                c[i][0]=0;
                for(i=0;i<=n;i++)
                                c[0][i]=0;
                for(i=1;i<=m;i++)
                                for(j=1;j<=n;j++)
                                {
                                                if(x[i-1]==y[j-1])
                                                {
                                                                c[i][j]=c[i-1][j-1]+1;
                                                                b[i][j]='c';
                                                }
                                                else if(c[i-1][j]>=c[i][j-1])
                                                {
                                                                c[i][j]=c[i-1][j];
                                                                b[i][j]='u';
                                                }
                                                else
                                                {
                                                                c[i][j]=c[i][j-1];
                                                                b[i][j]='l';
                                                }
                                }
                 print_lcs(m,n);
 }
void main()
{
                printf("Enter 1st sequence : ");
                gets(x);
                printf("Enter 2nd sequence : ");
                gets(y);
                printf("\n longest common sub-sequence is : ");
                lcs_length();
                getch();
}

Output:

LCS Output
Happy Coding

Related Post:

Topological sort of directed graph                                                                       

Longest Common Sub-sequence (LCS). In computer science we use dynamic programming for solving complex problem. A good example for dynamic programming is longest common subsequence. Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.