Longest Common Subsequence.

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.



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)

OUT:
SEQ1 : AMGGTABX_PYTHON
SEQ2 : GXNTXAYBX_PYTHON
Detected LCS: GTABX_PYTHON





See also related topics: