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

LCS problem is a dynamic programming approach in which we find the longest subsequence which is common in between two given strings. A subsequence is a sequence which appears in the same order but not necessarily contiguous. For example ACF, AFG, AFGHD, FGH are some subsequences of string ACFGHD. So for a string of length n there can be total 2^n subsequences. The LCS algorithm is widely used in bioinformatics.

For string ACFGHD and ABFHD, the longest common subsequence is AFHD. The function that is used to find the longest common subsequence of two strings is given below.

Below I have shared the C program for longest common subsequence problem and a video tutorial that will help you understand LCS algorithm easily.

## C Program for Longest Common Subsequence Problem

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#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**

brintoThanks

Manish kumarThanks

I likes your programing

shweta singhIt’s very easy to understand….thanks:)

BOLLAturedA

xshIn the main() function in the scanf() statement before x and y, ‘&'(ampersand) is missing…

AdminWhile reading string we dont have to use &.

coderCode is not giving exact answer for all the cases.

verify once again..

Ashikvery good

Genghisy did u use ‘c’,’u’,’l’ n how did the compiler come to know bout it????

AkashThanks for program..this is for my open ended problem.. thanks again

RonyYour logic behind this program is good bro but what if there are more then one lcs are possible. For example

I have

X = ABCBDAB

Y = BDCABA

LCS are:

BCBA

BCAB

BDAB

then how am i able to print them all ??