C Program for Longest Common Subsequence Problem

In this post, I am sharing the C program for the Longest Common Subsequence Problem.

LCS issue is a unique programming approach in which we locate the longest subsequence which is normal in the middle of two given strings. A subsequence is a grouping which shows up in a similar request however not really adjoining.

For instance, ACF, AFG, AFGHD, FGH are a few subsequences of string ACFGHD. So for a string of length n, there can be all-out 2^n subsequences. The LCS calculation is generally utilized in bioinformatics.

For string ACFGHD and ABFHD, the longest basic subsequence is ADHD. The capacity that is utilized to locate the longest basic subsequence of two strings is given underneath.

Underneath I have shared the C program for the longest basic subsequence issue and a video instructional exercise that will assist you with comprehension LCS calculation effectively.

C Program for Longest Common Subsequence Problem

#include<stdio.h>
#include<string.h>
 
int i,j,m,n,c[20][20];
char x[20],y[20],b[20][20];
 
void print(int i,int j)
{
                if(i==0 || j==0)
                                return;
                if(b[i][j]=='c')
                {
                                print(i-1,j-1);
                                printf("%c",x[i-1]);
                }
                else if(b[i][j]=='u')
                                print(i-1,j);
                else
                                print(i,j-1);
}
 
void lcs()
{
                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;
                                
                //c, u and l denotes cross, upward and downward directions respectively
                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';
                                                }
                                }
}
 
int main()
{
                printf("Enter 1st sequence:");
                scanf("%s",x);
                printf("Enter 2nd sequence:");
                scanf("%s",y);
                printf("\nThe Longest Common Subsequence is ");
                lcs();
                print(m,n);
		return 0;
}

Output

watch this video for more information