Find the longest common subsequence for the following two strings: X=ABACABB Y=BABCAB

343views

written 2.7 years ago by

binitamayekar ★ 6.6k

• modified 2.7 years ago

Longest Common Subsequence

The Longest Common Subsequence (LCS) is defined as the longest subsequence that is common to all the given strings provided.
But, the elements of the subsequence are not required to occupy consecutive positions within the original strings.
The longest common subsequence problem is finding the longest sequence which exists in both the given strings.

Steps involved in finding the Longest Common Subsequence (LCS) -

Step 1 - Create a table with dimension $[x+1*y+1]$ where x and y represent the lengths of strings X and Y respectively.

Step 2 - The first row and the first column are always filled with zeros.

Step 3 - Fill the entire table based on any of the following conditions:

IF Condition -

If the characters corresponding to the current row and current column are MATCHING, then fill the current cell by adding 1 to the value of a diagonal element.
Point an arrow to the diagonal cell.

ELSE Condition -

If the characters corresponding to the current row and current column are NOT MATCHING, then take the maximum value from the previous column and previous row element to fill the current cell.
If values of both previous column and row are same, then point to any of them.
Point an arrow to the cell with the maximum value.

Step 4 - Repeat step 3 until the entire table is filled.

Step 5 - The value in the last row and the last column represent the length of the longest common subsequence.

Step 6 - To find the longest common subsequence, start from the last element and follow the direction of the arrow.

Let's find out the longest common subsequence for the given strings step by step.

String X = ABACABB

String Y = BABCAB

Step 1 –

Create a table with dimension $[7 + 1 * 6 + 1] = [8 * 7]$

Because strings X and Y have the length of 7 and 8 respectively.

Step 2 –

Make the first row and the first column filled with zeros and called as Row -1 and Col -1.

The resultant table looks as follows:

LCS 1

Step 3 –

Row 0 Computation

LCS 2

In Row 0 & Col 0 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value and showing an arrow pointing to the previous row cell.
In Row 0 & Col 1 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (0 + 1 = 1) and show an arrow pointing to the diagonal cell.
In Row 0 & Col 2 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.
In Row 0 & Col 3 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.
In Row 0 & Col 4 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.
In Row 0 & Col 5 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (0 + 1 = 1) and show an arrow pointing to the diagonal cell.
In Row 0 & Col 6 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (0 + 1 = 1) and show an arrow pointing to the diagonal cell.

Step 4 –

Repeat step 3 until the entire table is filled.

Therefore,

Row 1 Computation

LCS 3

In Row 1 & Col 0 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (0 + 1 = 1) and show an arrow pointing to the diagonal cell.
In Row 1 & Col 1 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value and showing an arrow pointing to the previous row cell.
In Row 1 & Col 2 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (1 + 1 = 2) and show an arrow pointing to the diagonal cell.
In Row 1 & Col 3 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.
In Row 1 & Col 4 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (1 + 1 = 2) and show an arrow pointing to the diagonal cell.
In Row 1 & Col 5 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.
In Row 1 & Col 6 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.

Row 2 Computation

LCS 4

In Row 2 & Col 0 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 2 & Col 1 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (1 + 1 = 2) and show an arrow pointing to the diagonal cell.
In Row 2 & Col 2 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value and showing an arrow pointing to the previous row cell.
In Row 2 & Col 3 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value and showing an arrow pointing to the previous column cell.
In Row 2 & Col 4 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value and showing an arrow pointing to the previous column cell.
In Row 2 & Col 5 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (2 + 1 = 3) and show an arrow pointing to the diagonal cell.
In Row 2 & Col 6 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (2 + 1 = 3) and show an arrow pointing to the diagonal cell.

Row 3 Computation

LCS 5

In Row 3 & Col 0 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 3 & Col 1 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 3 & Col 2 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value and showing an arrow pointing to the previous row cell.
In Row 3 & Col 3 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (2 + 1 = 3) and show an arrow pointing to the diagonal cell.
In Row 3 & Col 4 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value (MAX) and showing an arrow pointing to the previous column cell.
In Row 3 & Col 5 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value and showing an arrow pointing to the previous column cell.
In Row 3 & Col 6 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value and showing an arrow pointing to the previous column cell.

Row 4 Computation

LCS 6

In Row 4 & Col 0 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (0 + 1 = 1) and show an arrow pointing to the diagonal cell.
In Row 4 & Col 1 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 4 & Col 2 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (2 + 1 = 3) and show an arrow pointing to the diagonal cell.
In Row 4 & Col 3 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column value and showing an arrow pointing to the previous column cell.
In Row 4 & Col 4 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (3 + 1 = 4) and show an arrow pointing to the diagonal cell.
In Row 4 & Col 5 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column (MAX) value and showing an arrow pointing to the previous column cell.
In Row 4 & Col 6 characters are NOT MATCHED. Therefore, fill the cell by taking the previous column (MAX) value and showing an arrow pointing to the previous column cell.

Row 5 Computation

LCS 7

In Row 5 & Col 0 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 5 & Col 1 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (1 + 1 = 2) and show an arrow pointing to the diagonal cell.
In Row 5 & Col 2 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 5 & Col 3 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value and showing an arrow pointing to the previous row cell.
In Row 5 & Col 4 characters are NOT MATCHED. Therefore, fill the cell by taking the previous row value (MAX) and showing an arrow pointing to the previous row cell.
In Row 5 & Col 5 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (4 + 1 = 5) and show an arrow pointing to the diagonal cell.
In Row 5 & Col 6 characters are MATCHED. Therefore, fill the cell by adding 1 to the value of the diagonal element (4 + 1 = 5) and show an arrow pointing to the diagonal cell.

Step 5 –

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

Therefore,

The length of the longest common subsequence for the given strings X & Y is 5.

Step 6 –

In order to find the longest common subsequence, start from the last element and follow the direction of the arrow and finally select the cells with diagonal arrows in the path.

LCS 8

Thus finally get the Longest Common Subsequence is BACAB.

ADD COMMENT EDIT