Longest Common Subsequence

 Longest Common Subsequence 

LCS Problem Statement: Given two sequences, find the length of  longest subsequence present in both of them. A subsequence is a  sequence that appears in the same relative order, but not necessarily  contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are  subsequences of “abcdefg”. 

Example 1: 

Input: text1 = "abcde", text2 = "ace"  

Output: 3  

Explanation: The longest common subsequence is "ace" and  its length is 3. 

Example 2: 

Input: text1 = "abc", text2 = "abc" 

Output: 3 

Explanation: The longest common subsequence is "abc" and  its length is 3. 

Example 3: 

Input: text1 = "abc", text2 = "def" 

Output: 0 

Explanation: There is no such common subsequence, so the  result is 0. 

Dynamic Programming 

Let A= <a1, a2, a3,…, am > and B = <b1, b2, b3,…, bn > be the  sequences. To compute the length of an element the following  algorithm is used. 

C[I,j] be a common sequence of A and B

Algorithm: LCS-Length-Table-Formulation (A, B) m := length(X)  

n := length(Y)  

for i = 1 to m do  

C[i, 0] := 0  

for j = 1 to n do  

C[0, j] := 0  

for i = 1 to m do  

 for j = 1 to n do  

 if ai = bj 

C[i, j] := C[i - 1, j - 1] + 1  

B[i, j] := ‘ ‘ 

 else  

 if C[i -1, j] ≥ C[i, j -1]  C[i, j] := C[i - 1, j]  

B[i, j] :=‘‘ ‘ 

 else  

C[i, j] := C[i, j - 1] 

B[i, j] := ‘ ‘ 

return C and B 

Algorithm to Print an LCS 

If i = 0 or j = 0 

Then return 

If B[i ,j] = “ “ 

Than print – LCS(B,A,i-1,j-1) 

Print ai 

Else if B [i,j] = := ‘‘ ‘ 

Then Print – LCS(B,A,i-1,j) 

Else Print-LCS(B,A,I,j-1)

Example 1 : 

Determine the LCS X = < C, R, O, S,S > and Y = < R, O, A, D,S > Solution: Here X = < C, R, O, S,S > , Y = < R, O, A, D,S > m = Length [X] = 5, n = length [Y] = 5 

Now fill the values of C[i,j] in m * n table 

Initially, for i =1 to C [ i, 0 ] =0 

For j = 0 to 6 C[0, j ] =0 

0 1 2 3 4 5 

yj R O A D S 

0 xi 1 C 2 R 3 O 4 S 5 S 

0	0	0	0	0	0
0	0	0	0	0	0
0	1	1	1	1	1
0	1	2	2	2	2
0	1	2	2	2	3
0	1	2	2	2	3

Length = 3

LCS = ROS 

Now, If i=1, j=1 , x1≠y1, C[i-1,j] >= C[i,j-1], Since, C[0,1] = C[1,0] =0 C[i,j] = C[i-1,j] 

So, C[1,1] = C[0,1]= 0 So B[1,1] = 0& ⬆️

Now i =1 , j = 2 & x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[0,2] = C[1,1] =0 So, C[1,2] =C[0,1]= B[1,2] = 0& ⬆️

Now i=1, j=3 & x1 ≠ y3& C[i-1,j] >= C[i,j-1] , Since, C[0,3] = C[1,2] =0 So C[1,3]= C[0,3] = 0 =B[1,3] =& ⬆️

Now i= 1, j =4 &C[0,4]=C[1,3] = 0 

C[1,4] = C[0,4] = 0 =B[1,4] = ⬆️

Now i= 1 , j =5&x1 ≠ y3 & C[i-1,j] >= C[i,j-1] = C[0,5] = C[0,5] = 0 C[1,5]= C[0,5] = 0= B[1,5] = ⬆️

Now i= 2 , j =1 & x2 = y1, C[i,j] = C[i-1,j-1] +1 &  ↖️

So C[2,1] = C[1,0] +1 =0+1 = 1 

Now i= 2 , j =2& x2 ≠ y2 

C[i-1,j]=C[1,2] = 0 & C[i,j-1] = C[2,1] = 1  

i.e. C[i-1,j]<C[I,j-1] 

C[i,j] = C[i, j-1] 

C[2,2] =C[2,1]= 1 = B[2,2] =  ⬅️

Now i= 2 , j =3 & x2 ≠ y3& C[i-1,j]<C[I ,j-1] 

So C[2,3] = C [2,2] = 1 = B[2,3] =  ⬅️

Now i= 2 , j =4& x2 ≠ y4& C[i-1,j] <C[I ,j-1] 

So C[2,4] = C [2,3] = 1 = B[2,4] =  ⬅️

Now i= 2 , j =5& x2 ≠ y4& C[i-1,j] <C[I ,j-1] 

So C[2,5] = C [2,4] = 1 = B[2,4] =  ⬅️

Now i= 3 , j =1& x1 ≠ y3& C[i-1,j] > C[i,j-1] = C[2,5] = 1 C[3,0] = 0 So C[3,1] =C[i-1,j] = C[2,1]= 1 & ⬆️

Now i= 3 , j =2& x2 = y1, C[i,j] = C[i-1,j-1] +1 & ↖️

C[3,2]= C[2,1]+1 = 1+1 =2  

Now i= 3 , j =3& x2 ≠ y3& C[i-1,j] <C[I ,j-1] , C[2,3]=1 &C[3,2]=2 C[i,j] = C[i,j-1] 

So C[3,3] = C [3,2] = 2 = B[2,3] = ⬅️ 

Now i= 3 , j =4& x2 ≠ y3& C[i-1,j] <C[I ,j-1] , C[2,3]=1 &C[3,3]=2 C[i,j] = C[i,j-1] 

So C[3,4] = C [3,3] = 2 = B[2,3] =  ⬅️

Now i= 3 , j =5& x2 ≠ y3& C[i-1,j] <C[I ,j-1] , C[2,3]=1 &C[3,4]=2 C[i,j] = C[i,j-1]

So C[3,5] = C [3,4] = 2 = B[2,3] =  ⬅️

Now i =4, j = 1& x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[3,1] =1& C[4,0] =0 C[i,j] = C[i-1,j]         ⬆️         

So, C[4,1] =C[3,1]= B[4,1] = 1&  ⬆️

Now i =4, j = 2 & x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[3,2] =2 & C[4,1] =1 C[i,j] = C[i-1,j]                                 ⬆️

So, C[4,2] =C[3,2]= B[4,2] = 2& ⬆️

Now i =4, j = 3 & x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[3,3] =2 & C[4,2] =1 C[i,j] = C[i-1,j]  ⬆️

So, C[4,3] =C[3,3]= B[4,3] = 2& ⬆️

Now i =4, j = 4 & x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[3,4] =2 & C[4,3] =1 C[i,j] = C[i-1,j]                                 ⬆️

So, C[4,4] =C[3,4]= B[4,3] = 2&  ⬆️

Now i= 4 , j =5& x2 = y1, C[i,j] = C[i-1,j-1] +1 &  ↖️

C[4,5]= C[3,4]+1 = 2+1 =3  ↖️

Now i =5, j = 1& x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[4,1] =1& C[5,0] =0 C[i,j] = C[i-1,j]              ⬆️

So, C[5,1] =C[4,1]= B[5,1] = 1 & ⬆️

Now i =5, j = 2 & x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[4,2] =2& C[5,1] =1 C[i,j] = C[i-1,j]                                     ⬆️

So, C[5,2] =C[4,2]= B[5,2] = 2 & ⬆️

Now i =5, j = 3 & x1 ≠ y2& C[i-1,j] >= C[i,j-1] , Since, C[4,3] =2& C[5,2] =2 C[i,j] = C[i-1,j]                             ⬆️

So, C[5,3] =C[4,3]= B[5,3] = 2 ⬆️

Now i =5, j = 4 & x5≠ y4& C[i-1,j] >= C[i,j-1] , Since, C[4,4] =2& C[5,3] =2 C[i,j] = C[i-1,j]                         ⬆️

So, C[5,4] =C[4,4]= B[5,4] = 2 ⬆️

Now i= 5 , j =5 & x5 = y5, C[i,j] = C[i-1,j-1] +1 &  ↖️

C[5,5]= C[4,4]+1 = 2+1 =3  

Example 2: 

Solve the following for obtaining the LCS X = < A, B, C, B, D, A, B> and  Y = < B, D, C, A, B, A > 

0 1 2 3 4 5 

yj B D C A B A 

0 xi 1 A 2 B 3 C 4 B 5 D 

 6 A  7 B 

Length = 4 LCS = BCBA

0	0	0	0	0	0	0
0	0	0	0	1	1	1
0	1	1	1	1	2	2
0	1	1	2	2	2	2
0	1	1	2	2	3	3
0	1	2	2	2	3	3
0	1	2	2	3	3	4
0	1	2	2	3	4	4

Example 3: 

Find the longest common subsequence between two sequence  S1 = { D,A,N,G,E,R } & S2 = {M,A,N,E,G,E,R} 

0 1 2 3 4 5 6 7 yj M A N E G E R 

0 xi 1 D 

2 A 

3 N 

4 G 5 E 

6 R 

Length = 5 LCS = ANGER

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	1	1	1	1	1	1
0	0	1	2	2	2	2	2
0	0	1	2	2	3	3	3
0	0	1	2	3	3	4	4
0	0	1	2	3	3	4	5

Example 4: 

Determine LCS of <1,0,0,1,0,1,0,1> and <0,1,0,1,1,0,1,1,0> 

Solution: 

X= <1,0,0,1,0,1,0,1>, Y= <0,1,0,1,1,0,1,1,0> 

0 1 2 3 4 5 6 7 8 9 yj 0 1 0 1 1 0 1 1 0 

0 xi 1 1 2 0 3 0 4 1 

5 0 61 70 8 1 

0	0	0	0	0	0	0	0	0	0
0
0
0
0
0
0
0
0