Home » Algorithms

Algorithm and procedure to solve a longest common subsequence problem

In this article, we are going to learn about Longest Common Subsequence (LCS) problem. Algorithm and procedure to solve a longest common subsequence problem using dynamic programming approach are also prescribed in this article.
Submitted by Abhishek Kataria, on August 02, 2018

Longest common Subsequence

Let X and Y be two subsequences and by LCS algorithm we can find a maximum length common subsequence of X and Y.
If |X|= m and |Y|= n then there is a 2m subsequence of x; we just compare each with Y (n comparisons).
So the running time of this particular algorithm will be O(n 2m).
LCS problem has an optimal substructure which means that the solution of the subproblem is parts of the final solution.
In this case, firstly it’s necessary to find the length of LCS then later we will modify the algorithm to find LCS itself.
For this define X_i, Y¬i to the prefixes of X and Y of length i and j respectively. Then define c[i,j] to be the length of LCS of X_i and Y_i.
Then the length of LCS of X and Y will be c[m, n].

i.e. c[i,j]= c[i-1,j-1]+1 if x[i]=y[j],
      C[i,j]= max(c[i,j-1],c[i-1,j]) otherwise

LCS Length Algorithm

    1.	m←length[X]
    2.	n←length[y]
    3.	let b[1…m,1…n]and c[0…m,0…n] be new tables
    4.	for i←1 to m
    5.	c[i,j]←0
    6.	do c[0,j]←0
    7.	for j← 0 to n
    8.	do c[0,j]←0
    9.	for i←1 to m
    10.	for j←1 to n
    11.	if xi=yi
    12.	then c[i,j]←c[i-1,j-1]+1
    13.	b[i,j]←”↖”
    14.	else if c[i-1,j]>=c[i,j-1]
    15.	then c[i,j]←c[i-1,j]
    16.	b[i,j]←”↑”
    17.	else c[i,j]←c[i,j-1]
    18.	b[I,j]←”←”
    19.	return c and b

Procedure of LCS

X and Y defined as a given X and Y set.
First design a, c and b table where Y set values will be present in column side and X set values will be present in row side.
Line 1 assigns the length of X into variable m, and in step 2 the length of Y will be assigned to variable n.
For loop present in line 3 and 4 is used to initialize all the first column value to zero.
Another for loop line 5-6 is used to initialize all the row values to zero.
In the given algorithm three arrows are used which are vertical, horizontal and semi-vertical. By using these arrows we have to find out the LCS element.
The loop present in line 7-16 is used to insert the numeric values with specific arrows in c and a table.

Complexity:

Complexity of longest common subsequence is O(mn). Where, m and n are length of two strings.