180120107023
Practical 12: LCS Problem
Aim: Write a Program for implement of LCS problem
Exercise:
#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;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
Analysis and Design of Algorithm
180120107023
{
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:
Analysis and Design of Algorithm
180120107023
Review Questions:
1. State the properties of Dynamic Programming Approach.
● Optimal Substructure: If an optimal solution contains optimal sub solutions
then a problem exhibits optimal substructure.
● Overlapping subproblems: When a recursive algorithm would visit the same
subproblems repeatedly, then a problem has overlapping subproblems.
2. Determine the Longest sequence of (A,B,C,D,B,A,C,D,F) and (C,B,A,F).
1 2 3 4 5 6 7 8 9
A[i] A B C D B A C D F
B[j] C B A F
Analysis and Design of Algorithm
180120107023
● We will build c [i, j] and d [i, j]. Initially c [i, 0] ← 0 where I represents row and c [0, j] ←
0 where j represent the column. The c table will store some values and d table will
store directions.
Step 1:
Step 2:
Analysis and Design of Algorithm
180120107023
As A [i] ≠ B [j]
If (c[0, 1] ≥ c [1, 0]) is true.
i.e. 0 ≥ 0
C [i, j] = c [i – 1, j]
C [1, 1] = c [0, 1]
C [1, 1] = 0
D [i, j] = ↑
Step 3:
Let i = 1, j = 2 then
As A [i] ≠ B [j]
If (c [i – 1, j] ≥ c [i, j - 1]) i.e. (c[0, 2] ≥ c [1, 1]) is true. i.e. 0 ≥0 C[i, j] = c [i –
1, j]
C[1, 2] = c [0, 2]
C[1, 2] = 0
Analysis and Design of Algorithm
180120107023
D[i, j] = ↑
Analysis and Design of Algorithm
