最长公共子序列问题和最小编辑距离源码

最长公共子序列（Longest Common Subsequence, LCS）问题是一个经典的计算机科学问题，它涉及到找出两个字符串中最长的共同子序列，即不考虑顺序但保持字符相同的子串。该问题通常用于比较文本相似度，特别是在生物信息学领域。

解决LCS问题最著名的算法是动态规划，比如可以使用Hunt-Szymanski算法或Floyd-Warshall算法的一种变体。在Python中，你可以使用以下简化的思路：

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    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])
    
    return dp[m][n]

# 示例
X = "ABCBDAB"
Y = "BDCABA"
print("Length of LCS is", lcs(X, Y))

最小编辑距离（Minimum Edit Distance,MED），也称为Levenshtein距离，是指将一个字符串转换成另一个字符串所需的最少单字符操作次数（插入、删除或替换）。同样，也可以通过动态规划求解。在Python中，可以用类似的方式来计算：

def min_edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    
    return dp[m][n]

# 示例
s1 = "kitten"
s2 = "sitting"
print("Minimum edit distance is", min_edit_distance(s1, s2))