# 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**and_{i}**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.

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!