По заданному списку строк s_0, s_1, ..., s_nнайдите самую короткую строку S, содержащую каждую из них s_0, s_1, ..., s_nв качестве подстроки .

Примеры :

• S('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')='SEDOLOREMAGNAD'
• S('ABCDE', 'BCD', 'C')='ABCDE'

Напишите самую короткую программу (или функцию), которая решает эту проблему. Вы можете представить строки в виде массивов или списков символов / целых чисел, если хотите. Стандартные библиотеки в порядке. Для ввода / вывода вы можете использовать все, что более удобно: STDIN / STDOUT, приглашение пользователя, параметр / возвращаемое значение функции и т. Д.

Производительность не критична - скажем, для ввода общей длины <100 символов результат должен быть вычислен за <10 секунд на среднем современном оборудовании.

Python 2, 170 153/157/159

Сокращено благодаря некоторым идеям Баптиста .

from itertools import*
print min((reduce(lambda s,w:(w+s[max(i*(s[:i]==w[-i:])for i in range(99)):],s)[w in s],p)
for p in permutations(input())),key=len)

Второй разрыв строки не нужен.

Вход: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Выход:SEDOLOREMAGNAD

Даже с длинными входными строками это выполняется менее чем за 2 секунды, если имеется не более 7 входных строк (как в случае с приведенным примером, который выполняется на моей машине за 1,7– 1,5 секунды). Однако при наличии 8 или более входных строк это занимает более 10 секунд, поскольку сложность по времени равна O(n!).

Как указал Баптист, его range(99)необходимо заменить на, range(len(w))если необходимо поддерживать произвольную длину ввода (общая длина кода 157 символов). Если должны поддерживаться пустые строки ввода, его следует заменить на range(len(w)+1). Я думаю, что range(99)работает правильно для любой общей длины ввода менее 200, хотя.

Больше тестов:

>>> "AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"
SEDOLOREMAGNAD

>>> 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 'abcdefghijklmnopqrstuvw
... xyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstu
... vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ZOOM', 'aZ', 'Za', 'ZA'
aZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZOOM

Mathematica 337 418 372

После неудачных попыток реализовать с помощью Mathematica LongestCommonSubsequencePositions, я обратился к сопоставлению с образцом.

v=Length;
p[t_]:=Subsets[t,{2}];
f[w_]:=Module[{c,x,s=Flatten,r={{a___,Longest[y__]},{y__,b___}}:>{{a,y},{y,b},{y},{a,y,b}}},
c=p@w;
x=SortBy[Cases[s[{#/.r,(Reverse@#)/.r}&/@c,1],{_,_,_,_}],v[#[[3]]]&][[-1]];
Append[Complement[w,{x[[1]],x[[2]]}],x[[4]]]]

g[r_]:=With[{h=Complement[r,Cases[Join[p@r,p@Reverse@r],y_/;!StringFreeQ@@y:>y[[2]]]]},
FixedPoint[f,Characters/@h,v@h-1]<>""]

Правило сопоставления с образцом,

r={{a___,Longest[y__]},{y__,b___}}:> {{a,y},{y,b},{y},{a,y,b}}},

принимает упорядоченную пару слов (представленных в виде списков символов) и возвращает: (1) слова, {a,y}а {y,b}затем (2) общую подстроку y, которая связывает конец одного слова с началом другого слова, и, наконец, объединенное слово {a,y,b}, которое заменит входные слова. См. Велизарий для соответствующего примера: /mathematica/6144/looking-for-longest-common-substring-solution

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

Reverseиспользуется позже, чтобы убедиться, что оба заказа проверены. Те пары, которые разделяют связываемые буквы, возвращаются без изменений и игнорируются.

Редактировать :

Следующее удаляет из списка слова, которые «похоронены» (то есть полностью содержатся) в другом слове (в ответ на комментарий @ flornquake).

h=Complement[r,Cases[Join[p@r,p@Reverse@r],x_/;!StringFreeQ@@x:> x[[2]]]]

Пример :

 {{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}} /. r

возвращается

{{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}, { "L", "O", "R", "E"}, {"D", "O", "L", "O", "R", "E", "M"}}

использование

g[{"LOREM", "ORE", "R"}]

AbsoluteTiming[g[{"AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"}]]

"Lorem"

{0.006256, "СЕДОЛОРЕМАГНАД"}

GolfScript, 66 символов

{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=

Довольно короткий, но из-за экспоненциальной сложности времени (и GolfScript) очень медленный, он преодолевает 10-секундный лимит времени.

Примеры:

['LOREM' 'DOLOR' 'SED' 'DO' 'MAGNA' 'AD' 'DOLORE']
{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=
# => SEDOLOREMAGNAD

['AB' 'BC' 'CA' 'BCD' 'CDE']
{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=
# => CABCDE

Python 2, 203 187 200

from itertools import permutations as p
def n(c,s=''):
 for x in c:s+=x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if s.endswith(l)),0):]
 return s
print min(map(n,p(input())),key=len)

Вход: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Выход:SEDOLOREMAGNAD

редактировать

Используя reduceи некоторые грязные хитрости импорта, я могу уменьшить это (и только до одной строки!):

print min((reduce(lambda a,x:a+x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],P,'')for P in __import__('itertools').permutations(input())),key=len)

Редактировать 2

Как отметил flornquake, это дает неверные результаты, когда одно слово содержится в другом. Исправление для этого добавляет еще 13 символов:

print min((reduce(lambda a,x:a+(x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],'')[x in a],P,'')for P in __import__('itertools').permutations(input())),key=len)

Вот очищенная версия:

from itertools import permutations

def solve(*strings):
    """
    Given a list of strings, return the shortest string that contains them all.
    """
    return min((simplify(p) for p in permutations(strings)), key=len)

def prefixes(s):
    """
    Return a list of all the prefixes of the given string (including itself),
    in ascending order (from shortest to longest).
    """
    return [s[:i+1] for i in range(len(s))]
    return [(i,s[:i+1]) for i in range(len(s))][::-1]

def simplify(strings):
    """
    Given a list of strings, concatenate them wile removing overlaps between
    successive elements.
    """
    ret = ''
    for s in strings:
        if s in ret:
            break
        for i, prefix in reversed(list(enumerate(prefixes(s)))):
            if ret.endswith(prefix):
                ret += s[i+1:]
                break
        else:
            ret += s
    return ret

print solve('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')

Можно сбрить несколько персонажей ценой теоретической правильности, используя range(99)вместо range(len(x))(кредиты за флорбакет за размышления об этом).

Питон, 144 символа

S=lambda A,s:min(S(A-set([a]),s+a[i:])for a in A for i in range(len(a)+1)if i==0 or s[-i:]==a[:i])if A else(len(s),s)
T=lambda L:S(set(L),'')[1]

Sпринимает набор слов, Aкоторые все еще нуждаются в размещении, и строку, sсодержащую слова, размещенные до сих пор. Мы выбираем оставшееся слово aиз Aи накладываем его 0на len(a)символы с окончанием s.

Занимает всего около 0,15 секунд на данном примере.

Хаскелл, 121

import Data.List
a p []=[(length p,p)]
a p s=[r|w<-s,t<-tails w,isInfixOf w$p++t,r<-a(p++t)(s\\[w])]
s=snd.minimum.a ""

Минус два, если функция не должна быть привязана к имени