longest_common_subsequence.py

# Longest Common Subsequence (LCS) using Dynamic Programming

def lcs(X, Y):
    m, n = len(X), len(Y)

    # DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Backtracking to get LCS string
    i, j = m, n
    lcs_seq = []

    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_seq.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs_seq.reverse()

    return dp[m][n], "".join(lcs_seq)


# -------- Input --------
X = input("Enter first sequence: ")
Y = input("Enter second sequence: ")

length, sequence = lcs(X, Y)

# -------- Output --------
print("Length of LCS:", length)
print("LCS:", sequence)