How to implement Longest Common Subsequence in Python

This Python tutorial will help you to understand what is Longest Common Subsequence and how Python implements this algorithm. First, we will learn what is longest common subsequence.

Find Longest Common Subsequence in Python

Definition :

Longest Common Subsequence determines the longest sequence which exists in both the given strings. A subsequence or a substring can be formed from a string or a sequence.

Example:-

Let’s say,

Input :

Sequence – 1 : ‘BACDBAD’

Sequence – 2 : ‘BCABDBC’

Output :

The longest common subsequence from the above two strings or two sequences is ‘BCAD’.

Applications of LCS:

• Forms the basis for data comparison which will be used in the field of bioinformatics.
• Also widely used by revision control systems such as Git.

Implementation of LCS in Python

Source Code: Python

def lcs(str1, str2):
    a = len(str1)
    b = len(str2)

    string_matrix = [[0 for i in range(b+1)] for i in range(a+1)]   

    for i in range(1, a+1):
        for j in range(1, b+1):

            if i == 0 or j == 0:
                string_matrix[i][j] = 0

            elif str1[i-1] == str2[j-1]:
                string_matrix[i][j] = 1 + string_matrix[i-1][j-1]

            else:
                string_matrix[i][j] = max(string_matrix[i-1][j], string_matrix[i][j-1])

    index = string_matrix[a][b]

    res = [""] * index
    i = a
    j = b

    while i > 0 and j > 0:
        if str1[i-1] == str2[j-1]:
            res[index-1] = str1[i-1]
            i -= 1
            j -= 1
            index -= 1

        elif string_matrix[i-1][j] > string_matrix[i][j-1]:
            i -= 1
        else:
            j -= 1

    return res


if __name__ == '__main__':
    str1 = "acbaed"
    str2 = "abcadf"

    string1 = ''.join(lcs(str1, str2))
    print("Length of LCS is:", len(string1),"\nsubsequence is:", string1)
    
    
    
    str3 = "ABAZDC"
    str4 = "BACBAD"
    
    string2 = ''.join(lcs(str3, str4))
    print("Length of LCS is:", len(string2),"\nsubsequence is:", string2)

Output :

Case -1 :-
Input :
str1 = "acbaed"
str2 = "abcadf"

Output :
Length of LCS is: 4                                                                                                     
subsequence is: abad

Case -2 :-

Input :
str3 = "ABAZDC"
str4 = "BACBAD"

Output :
Length of LCS is: 4                                                                                                     
subsequence is: ABAD

You can also read,

• How to implement Minimum Edit Distance in Python
• How to implement Dijkstra’s shortest path algorithm in Python