Longest Common Subsequence�

• The longest common subsequence problem is finding the longest sequence which exists in both the given strings.

Subsequence

• Let us consider a sequence S = <s₁, s₂, s₃, s₄, …,s_n>.
• A sequence Z = <z₁, z₂, z₃, z₄, …,z_m> over S is called a subsequence of S, if and only if it can be derived from S by deletion of some elements.

​

Amity School of Engineering & Technology

Common Subsequence�

Suppose, X and Y are two sequences over a finite set of elements. We can say that Z is a common subsequence of X and Y, if Z is a subsequence of both X and Y.

Longest Common Subsequence:-

• If a set of sequences are given, the longest common subsequence problem is to find a common subsequence of all the sequences that is of maximal length.

​

Amity School of Engineering & Technology

Steps

The following steps are followed for finding the longest common subsequence in string X and Y.

1. Create a table of dimension n+1*m+1 where n and m are the lengths of X and Y respectively. The first row and the first column are filled with zeros.�

Amity School of Engineering & Technology

2. Fill each cell of the table using the following logic

• If the character corresponding to the current row and current column are matching, then fill the current cell by adding one to the diagonal element. Point an arrow to the diagonal cell.
• Else take the maximum value from the previous column and previous row element for filling the current cell. Point an arrow to the cell with maximum value.� If they are equal, point to any of them.

​

Amity School of Engineering & Technology

3. Step 2 is repeated until the table is filled.

4. The value in the last row and the last column is the length of the longest common subsequence.

5.In order to find the longest common subsequence, start from the last element and follow the direction of the arrow. The elements corresponding to diagonal arrow form the longest common subsequence.

Amity School of Engineering & Technology

Example�

X = BACDB 

Y = BDCB

Amity School of Engineering & Technology

Answer

• Length- 3
• BDB or BCB

Amity School of Engineering & Technology

Problem

X = ACADB

Y = CBDA

​

Amity School of Engineering & Technology

Answer

• Length-2
• CA or CB or CD

Amity School of Engineering & Technology