python - 找到两个字符串之间的最佳匹配字符数（类似于字符串对齐，但在某些方面不是）

Question

我正在尝试在 Python 中执行此操作。我有两个序列：

seq1: 'ABCD E'

seq2：'ARCB E'

假设我想“计算” seq1 和 seq2 中的字符数，但按照以下方式，假设我从 seq1 中的 A 到 seq2 中的 A 画一条线，同样连接 C--C 和 E--E 但如果我连接 B--B 这条连接线将越过连接 C--C 的线，所以......我想计算 B---B 或 C--C 而不是两者，因为它们的线交叉并找到这样的总数我可以在两个字符串之间建立连接。

有没有办法做到这一点？我确信我正在尝试做的事情有一个名字，但我不知道它，这使得在线搜索可能的方法也很困难。

感谢您的帮助。

Answer 1

听起来像是最长的公共子序列问题。Levenshtein 距离的动态规划算法的简化版本解决了这个问题。

互联网上有大量 LCS的Python 实现。维基百科给出的伪代码翻译成 Python 也很简单。