查找两个字符串之间的最佳匹配字符数(类似于字符串对齐，但在某些方面并非如此)

问题描述

我正尝试用Python来做这件事。 我有两个序列：

序列1：‘A B C D E’

序列2：‘A R C B E’

假设我要"计算"seq1和seq2中的字符数 但是在下面的方法中，假设我从序列1中的A到序列2中的A画一条线，同样连接C--C和E--E，但是如果我连接B-B，这条连接线将跨越连接C-C的线，所以。 我想要计算B-B或C--C，而不是两者，因为它们的线交叉，并找出我可以在两个字符串之间建立的此类连接的总数。

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

感谢您的帮助。

---

解决方案

听起来像longest common subsequence问题。Levenshtein距离的动态规划算法的简化版本解决了这个问题。

互联网上有许多Python implementations of LCS。维基百科提供的伪代码对于翻译成Python来说也是微不足道的。