C Program for Longest Common Subsequence problem
Here in this post you will learn C program for Longest Common Subsequence Problem.
The Longest Common Subsequence (LCS) problem is a classic problem in dynamic programming. Given two sequences, it seeks the longest subsequence that appears in both sequences in the same relative order but not necessarily contiguous.
For example, consider two sequences:
Sequence 1: ABCDEFG
Sequence 2: ABDFFGH
In this case, the longest common subsequence would be “ABFG” with a length of 4.
Dynamic programming is often used to solve this problem efficiently. The key idea is to build a table where each cell stores the length of the longest common subsequence found so far for the corresponding prefixes of the two sequences.
Example of 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 | #include<stdio.h> #include<string.h> int i,j,m,n,c[30][30]; char x[30],y[30],b[30][30]; 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; 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("Please input 1st sequence :"); scanf("%s",x); printf("Please input 2nd sequence :"); scanf("%s",y); printf("\nThe Longest Common Subsequence is : "); lcs(); print(m,n); return 0; } |
Output
Please input 1st sequence :ASFHJK
Please input 2nd sequence :RASOJK
The Longest Common Subsequence is : ASJK
Read Also
Implement N Queens Problem using Backtracking
Knapsack Problem Using Greedy Solution
1/2 Knapsack Problem Using Dynamic Programming