Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is a classic computer science problem for finding the length of longest possible common subsequence from a set of subsequence to the given two sequences.
Longest Common Subsequence (LCS) problem can be solved by many different approaches.But the most efficient approach to solve the Longest Common Subsequence (LCS) problem is Dynamic programming approach which takes the O(N * M) time complexity, where N and M are the sizes of the given sequences.

Problem Statement

Given two sequences, and the task is to find the length of the longest subsequence that is present in subsequence of the two sequences.

Longest Common Subsequence Example

Below is the example of Longest Common Subsequence Problem with input- output constraint and the solution for the example using the Dynamic programming approach.

Input – Output Data for the Algorithm

• Subs_1 : This contains the first sequence.
• Subs_2 : This contains the second sequence.
• N : This contains the size of the first sequence.
• M : This contains the size of the second sequence.
• Table[] : This contains the Array to solve the problem.
• Solution : This is used to store the number required.

Input and Output of the Example

Given two sequence, Subs_1 = “ABC” and Subs_2 = “BCD” of size N = 3 and and M = 3, the task is to find the length of Longest Common Subsequence possible.

Answer: 2
A Longest Common Subsequence is BC

Steps to solve the problem

There are two cases, the last characters match or the last characters do not match.

1. If it matches, then increment the length of LCS[i][j] by 1 and process Subs_1[i-1] and Subs_2[j-1].
2. If it is not match, then find the max of L[i-1][j] and L[i][j-1].

Stepwise Solution of the Longest Common Subsequence Problem Example

Solution of the above example using the Dynamic programming approach.
Given data are

1.Create a LCS[N+1][M+1] where First column represents the String 1 and First Row represents the String 2 with additional Value( empty value) in both. And fill up in bottom up manner.

2.For first element of Subs_2 = B, do the matching with each element of Subs_1. An follow the steps that are given below.

• B does not match with Subs_1[1] = A, then max of left and right cell is 0.
• B matches with Subs_1[2] = B, then 1 + diagonal cell is 1.
• B not match with Subs_1[3] = C, then max of left and right cell is 1.

3.For element of Subs_2 = C, do the matching with each element of Subs_1. An follow the steps that are given below.

• C does not match with Subs_1[1] = A, then max of left and right cell is 0.
• C not match with Subs_1[2] = B, then max of left and right cell is 1.
• C matches with Subs_1[3] = C, then 1 + diagonal cell is 2.

4.For element of Subs_3 = D, do the matching with each element of Subs_1. An follow the steps that are given below.

• D does not match with Subs_1[1] = A, then max of left and right cell is 0.
• D not match with Subs_1[2] = B, then max of left and right cell is 1.
• D not match with Subs_1[3] = C, then max of left and right cell is 2.

Pseudocode for Longest Common Subsequence Problem using Dynamic programming

Here’s Pseudocode for solving the Longest Common Subsequence Problem using Dynamic programming.

function Longest_Common_Subsequence_Length(Subs_1[1..m], Subs_2[1..n])
    Table = array(0..m, 0..n)
    for i := 0..m
        Table[i,0] = 0
    for j := 0..n
        Table[0,j] = 0
    for i := 1..m
        for j := 1..n
            if Subs_1[i] = Subs_2[j] //i-1 and j-1 if reading Subs_1 & Subs_2 from zero
                Table[i,j] := Table[i-1,j-1] + 1
            else
                Table[i,j] := max(Table[i,j-1], Table[i-1,j])
    return Table[m,n] 

Implementation of Longest Common Subsequence Problem using Dynamic programming in Python

# Implementation of Longest_Common_Subsequence problem 

def Longest_Common_Subsequence(Subs_1, Subs_2, M, N):

    # 2array to store DP value
    Table = [[None]*(N+1) for i in range(M+1)] 

    for i in range(M+1): 
        for j in range(N+1): 
            if i == 0 or j == 0 : 
                Table[i][j] = 0
            elif Subs_1[i-1] == Subs_2[j-1]: 
                Table[i][j] = 1 + Table[i-1][j-1]
            else: 
                Table[i][j] = max(Table[i][j-1], Table[i-1][j]) 
    return Table[M][N] 

# Given two sequence and their size
Subs_1 = "PREPTECH"
Subs_2 = "PREPFORTECH"
N = len(Subs_1) 
M = len(Subs_2) 

# function calling
Solution = Longest_Common_Subsequence(Subs_1, Subs_2, N, M) 

# Printing the Solution
print(Solution)