python中粗略的字符串对齐方式

Question

如果我有两个相同长度的字符串,如下所示:

'aaaaabbbbbccccc'
'bbbebcccccddddd'

是否有一种有效的方法来对齐两者,使得尽可能多的字母排列如下所示？

'aaaaabbbbbccccc-----'
'-----bbbebcccccddddd'

我能想到这样做的唯一方法是通过编辑字符串然后迭代和比较来进行蛮力.

Answer 1

返回给出最大分数的索引，其中最大分数是具有最多匹配字符的字符串。

def best_overlap(a, b):
    return max([(score(a[offset:], b), offset) for offset in xrange(len(a))], key=lambda x: x[0])[1]

def score(a, b):
    return sum([a[i] == b[i] for i in xrange(len(a))])

>>> best_overlap(a, b)
5
>>> a + '-' * best_overlap(a, b); '-' * best_overlap(a, b) + b
'aaaaabbbbbccccc-----'
'-----bbbebcccccddddd'

或者，等效地：

def best_match(a, b):
    max = 0
    max_score = 0
    for offset in xrange(len(a)):
        val = score(a[offset:], b)
        if val > max_score:
            max_score = val
            max = offset
    return max

还有优化的空间，例如：

1. 由于没有匹配的字符而提前退出

2. 当找到最大可能的匹配时提前退出