找到两个字符串之间的最佳匹配字符数(类似于字符串对齐但不是某些方面)

use*_*355 1 python string match

我试图用Python做到这一点.我有两个序列:

seq1:'ABCDE'

seq2:'ARCBE'

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

有没有办法做到这一点?我确信我要做的事情有一个名字,但我不知道,这使得在线搜索可能的方法也很困难.

感谢您的帮助.

Fre*_*Foo 5

听起来像是最常见的子序列问题.Levenshtein距离的动态编程算法的简化版本解决了这个问题.

互联网上有许多LCSPython实现.维基百科提供的伪代码也很容易翻译成Python.