python - 具有最小纠错的两个序列之间的最长公共子串

Question

我有两个字符串 A 和 B。我想找到这两个字符串之间最长的公共子字符串，同时允许 B 或 A 中的最小错误纠正。错误以相邻交换的形式出现，例如s_1s_2...s_i s_{i+1}...s_n与字符串 1 个交换s_1s_2...s_{i+1} s_{i}...s_n。是否有任何动态编程解决方案？

在两个字符串中匹配一个字母的分数是 M，交换的惩罚是 P。所以总的来说，目标是最大化总 M - P。显然，如果我在 A 中交换两个相邻的字母并且在 B 中有一个匹配这些字母，那么分数将增加 2M - P。

我已经编写了一个用于计算 LCS 的递归代码，但我不知道如何添加交换校正。

M = 1 # score for matching a letter in two strings
P = 1 # penalty for swapping

def lcs(A, B, i, j, res):
    if i == -1 or j == -1:
        return res
    if A[i] == B[j]:
        res = lcs(A, B, i - 1, j - 1, res + M)
    return max(res, max(lcs(A, B, i, j - 1, 0), lcs(A, B, i - 1, j, 0)))


>>> A = "fghijklmnopq"
>>> B = "klmnopqrstuv"
>>> res = lcs(A, B, len(A) - 1, len(B) - 1, 0)
>>> print(res)
7

标签： pythonalgorithmdynamic-programming