LCS problem use case.
In computer science and programming, he longest common subsequence or simply LCS problem is the problem of finding the longest subsequence common to all sequences in a set of sequences, e.g. two sequences.
LCS Problem formulation: having two input sequences, find the length of longest subsequence contained in both of them.
A subsequence is a sequence that appears in the same relative order, but not necessarily strictly contiguous, i.e.
the elements of the subsequence are not required to occupy consecutive positions within the original sequences.
Python Knowledge Base: Make coding great again.
- Updated:
2024-10-14 by Andrey BRATUS, Senior Data Analyst.
Longest Common Subsequence Python code:
Longest Common Subsequence code output:
The longest common subsequence problem is a typical computer science problem which solution and implementation has many real life use cases in programming world starting from text processors differences comparison functionality, revision control systems ( e.g. GIT), linguistics and genome study models.
def lcs(SEQ1, SEQ2, m, n):
L = [[0 for x in range(n+1)] for x in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif SEQ1[i-1] == SEQ2[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
index = L[m][n]
lcs = [""] * (index+1)
lcs[index] = ""
i = m
j = n
while i > 0 and j > 0:
if SEQ1[i-1] == SEQ2[j-1]:
lcs[index-1] = SEQ1[i-1]
i -= 1
j -= 1
index -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
print("SEQ1 : " + SEQ1 + "\nSEQ2 : " + SEQ2)
print("Detected LCS: " + "".join(lcs))
# Test data
SEQ1 = "AMGGTABX_PYTHON"
SEQ2 = "GXNTXAYBX_PYTHON"
m = len(SEQ1)
n = len(SEQ2)
lcs(SEQ1, SEQ2, m, n)
OUT:
SEQ1 : AMGGTABX_PYTHON
SEQ2 : GXNTXAYBX_PYTHON
Detected LCS: GTABX_PYTHON