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.
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.
Longest Common Subsequence Python code:
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)
SEQ1 : AMGGTABX_PYTHON
SEQ2 : GXNTXAYBX_PYTHON
Detected LCS: GTABX_PYTHON