diff.py

def lcs_diff(seq1, seq2):
    m, n = len(seq1), len(seq2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if seq1[i - 1] == seq2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Backtrack to find the LCS and diff
    i, j = m, n
    lcs = []
    while i > 0 and j > 0:
        if seq1[i - 1] == seq2[j - 1]:
            lcs.append(seq1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs.reverse()

    # Now we have the LCS, we can generate diffs
    diff = []
    i, j = 0, 0
    for char in lcs:
        while seq1[i] != char:
            diff.append(f"- {seq1[i]}")
            i += 1
        while seq2[j] != char:
            diff.append(f"+ {seq2[j]}")
            j += 1
        i += 1
        j += 1
    
    while i < m:
        diff.append(f"- {seq1[i]}")
        i += 1
    while j < n:
        diff.append(f"+ {seq2[j]}")
        j += 1

    return diff

# Example usage
seq1 = "abcdefg"
seq2 = "acdfgh"
diff_result = lcs_diff(seq1, seq2)
for line in diff_result:
    print(line)