# 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 Xi, 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 Xi and Yi.
• 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

1. X and Y defined as a given X and Y set.
2. 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.
3. Line 1 assigns the length of X into variable m, and in step 2 the length of Y will be assigned to variable n.
4. For loop present in line 3 and 4 is used to initialize all the first column value to zero.
5. Another for loop line 5-6 is used to initialize all the row values to zero.
6. 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.
7. 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.

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates