Categories: Dynamic Programming Programming

Longest Common Subsequence Approach Explained

This type of problem can be solved easily using Dynamic Programming. In this problem, you are generally given two sequences and you need to find the length of the common subsequence present in them. These type of problem finds usage in bioinformatics.

Related Post

A sub-sequence may be defined as the sequence that appear in relatively same order but not necessarily continuous. E.g.”abd” and “abc” are subsequences of “abdcfgrhd” .

Procedure

  1. Make a (len_substr_x * len_substr_y ) matrix of zeroes.
  2. If the x[i] == y[j] of the substrings match. Increment the value of the value of matrix at (i, j) by 1.
  3. Else fill the matrix at (i, j) with the value of largest adjacent matrix cell.
  4. The value at ( len_substr_x – 1, len_substr_y – 1) gives us the length of largest substring.
Longest common sub-sequence

Code

###################### longest common subsequence ########################

def solve(x,y):
    len_x = len(x)
    len_y = len(y)

    # creating a Matrix
    mat = [[0] * (len_y) for i in range(len_x)]
    sequence = []

    for i in range(len_x):
        for j in range(len_y):
            if x[i] == y [j]:
                mat[i][j] = mat[i-1][j-1] + 1
                sequence.append(x[i])
            else:
                mat[i][j] = max(mat[i - 1][j], mat[i][j - 1])
           
    return mat[len_x-1][len_y-1]


if __name__ == "__main__":
    x = 'abrxrxr'
    y = 'abtdrrxxr'
    print(solve(x,y))
Aditya Kumar

Share
Tags: dynamic programming Python

Recent Posts

  • Programming

Mastering Print Formatting in Python: A Comprehensive Guide

In Python, the print() function is a fundamental tool for displaying output. While printing simple…

8 months ago
  • Programming

Global Variables in Python: Understanding Usage and Best Practices

Python is a versatile programming language known for its simplicity and flexibility. When working on…

8 months ago
  • Programming

Secure Your Documents: Encrypting PDF Files Using Python

PDF (Portable Document Format) files are commonly used for sharing documents due to their consistent…

8 months ago
  • Programming

Creating and Modifying PDF Files in Python: A Comprehensive Guide with Code Examples

PDF (Portable Document Format) files are widely used for document exchange due to their consistent…

8 months ago
  • Programming

Boosting Python Performance with Cython: Optimizing Prime Number Detection

Python is a high-level programming language known for its simplicity and ease of use. However,…

8 months ago
  • Programming

Using OOP, Iterator, Generator, and Closure in Python to implement common design patterns

Object-Oriented Programming (OOP), iterators, generators, and closures are powerful concepts in Python that can be…

8 months ago

This website uses cookies.