How to implement Longest Common Subsequence in Python
By Abhilash BandlaThis 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,
Leave a Reply