- [email protected]
- April 14, 2023
- 11:54 am
- No Comments
LCS Problem Code With Python
T
The longest common subsequence (LCS) is defined as the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences.
If S1 and S2 are the two given sequences then, Z is the common subsequence of S1 and S2 if Z is a subsequence of both S1 and S2. Furthermore, Z must be a strictly increasing sequence of the indices of both S1 and S2.
Objective
The objective of the Longest Common Subsequence (LCS) problem is to find the longest subsequence that is present in two given strings. A subsequence is a sequence of characters that appears in the same order, but not necessarily consecutively, in both strings. The LCS problem is commonly used in areas such as bioinformatics, where it can be used to compare DNA sequences, and in data compression, where it can be used to find the similarities between two files and compress them accordingly.
def lcs(x, y):
# Get the length of strings x and y
m = len(x)
n = len(y)
# Create a 2D list of size (m+1)x(n+1) and initialize it with 0's
L = [[0] * (n + 1) for i in range(m + 1)]
# Fill the L table using dynamic programming to find the longest common subsequence
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
# If the characters at position i-1 in x and j-1 in y are equal,
# the length of the longest common subsequence is the length of
# the longest common subsequence of the prefixes without these characters,
# plus 1
L[i][j] = L[i - 1][j - 1] + 1
else:
# If the characters at position i-1 in x and j-1 in y are not equal,
# the length of the longest common subsequence is the maximum of
# the length of the longest common subsequence of the prefix of x
# without the current character, and the length of the longest
# common subsequence of the prefix of y without the current character
L[i][j] = max(L[i - 1][j], L[i][j - 1])
# Reconstruct the longest common subsequence using the L table
index = L[m][n]
lcs = [""] * index
i = m
j = n
while i > 0 and j > 0:
if x[i - 1] == y[j - 1]:
# If the characters at position i-1 in x and j-1 in y are equal,
# add this character to the longest common subsequence and
# move diagonally to the previous prefix
lcs[index - 1] = x[i - 1]
i -= 1
j -= 1
index -= 1
elif L[i - 1][j] > L[i][j - 1]:
# If the length of the longest common subsequence of the prefix of x
# without the current character is greater than the length of the
# longest common subsequence of the prefix of y without the current character,
# move upwards to the previous prefix of x
i -= 1
else:
# Otherwise, move leftwards to the previous prefix of y
j -= 1
# Print the longest common subsequence and return it as a string
print("Longest Common Subsequence:", "".join(lcs))
return "".join(lcs)