Python将字符串组合成尽可能短的字符串？

Question

如果我有一个字符串列表，我想将它们组合成一个具有重叠字符的字符串。如果没有重叠的字符串，只需将其添加到末尾。这是一个过于简化的版本。在

input = ['one', 'two']
output = 'twone'

我要寻找的方法是用输入列表中任意数量的字符串来实现这一点。在

谢谢，
乔达梅里奥

Answer 1

仅仅举一个小例子还不够好。这是农历年中最不明确的问题。但是，假设重叠只能出现在结尾处，并且每个单词只测试两次（针对当前输出的每一端），并且您想要最大的重叠，则这将完成以下工作：

[修复错误后编辑]

def glue(a, b):
    maxn = 0
    for n in xrange(1, 1 + min(len(a), len(b))):
        suffix = a[-n:]
        prefix = b[:n]
        if prefix == suffix:
            maxn = n
    # BUG: return maxn, a[:-maxn] + b
    # FAILS when maxn == 0
    # EXTRA TEST: ['nil', 'overlap']
    return a + b[maxn:]     


def multiglue(words):
    if not words: return ""
    result = words[0]
    for word in words[1:]:
        nx, rx = glue(result, word)
        ny, ry = glue(word, result)
        result = rx if nx > ny else ry
    return result

tests = [line.split() for line in """
    one
    two one
    one two
    overlap nil
    nil overlap
    toad dog rabbit
    frog ogham
    ogham frog
    hopper grasshopper
    grass grasshopper person
    foooo oooof
    oooof foooo""".splitlines()]

for test in tests:
    out = multiglue(test)
    print test, repr(out)

输出：

^{pr2}$

Answer 2

您应该能够使用Needleman-Wunsch algorithm的修改版本。从你的问题中我不清楚组合字符串必须满足什么约束条件（一个字符串必须嵌入另一个字符串中，还是一个字符串中的字符可以与另一个字符串中的字符混合？），所以我不会为您修改它，但至少应该足以让您开始。在

见http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm

还有，http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf