Python Объединение строк в кратчайшую строку?

Question

Если у меня есть список строк, я хотел бы объединить их в одну строку с перекрывающимися символами. Если не осталось перекрывающихся строк, просто добавьте его в конец. Вот слишком упрощенная версия.

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

То, что я ищу, как способ сделать это с любым количеством строк в списке ввода.

Спасибо,
giodamelio

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)

Вывод:

[] ''
['one'] 'one'
['two', 'one'] 'twone'
['one', 'two'] 'twone'
['overlap', 'nil'] 'niloverlap'
['nil', 'overlap'] 'overlapnil'
['toad', 'dog', 'rabbit'] 'rabbitoadog'
['frog', 'ogham'] 'frogham'
['ogham', 'frog'] 'frogham'
['hopper', 'grasshopper'] 'grasshopper'
['grass', 'grasshopper', 'person'] 'grasshopperson'
['foooo', 'oooof'] 'foooof'
['oooof', 'foooo'] 'foooof'

Answer 2

Вы сможете использовать модифицированную версию алгоритма Needleman-Wunsch . Из вашего вопроса мне не ясно, каким ограничениям должна удовлетворять объединенная строка (одна строка должна вставлять целую в другую, или символы из одного смешиваются из символов из другого?), Поэтому я не буду ее изменять Вы, но этого должно быть достаточно, чтобы начать, по крайней мере.

См. http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm

Также http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf