我正在尝试在python中这样做。我有两个序列:
seq1:'a b c d e'
seq2:'a r c b e'
假设我想"计数" seq1和seq2中的字符数但是,以下面的方式,假设我绘制了从seq1中的一条线到seq2中的一个,并且同样连接c-c和e-e,但是如果我连接b-b,则此连接线将越过链接C--的线路c所以...我想计算b --- b或c-c,而不是因为它们的线路交叉并找到我可以在两个字符串之间建立的这种连接的总数。
有办法做到这一点吗?我敢肯定,我想做的是一个名字,但我不知道,这也使在线搜索可能的方法也很困难。
谢谢您的帮助。
听起来像是最长的常见子序列问题。Levenshtein距离的动态编程算法的简化版本解决此问题。
Interwebs上有许多LCS的Python实现。Wikipedia给出的伪代码也很难翻译成Python。