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.
![Longest Common Subsequence.](https://python-code.pro/static/memes/longest-common-subsequence.webp)
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 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