Dada una lista de cadenas, s_0, s_1, ..., s_nencuentre la cadena más corta Sque contenga cada una de ellas s_0, s_1, ..., s_ncomo una subcadena .

Ejemplos :

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

Escriba el programa (o función) más corto que resuelva este problema. Puede representar cadenas como matrices o listas de caracteres / enteros si lo desea. Las bibliotecas estándar están bien. Para entrada / salida, puede usar lo que sea más conveniente: STDIN / STDOUT, indicador de usuario, parámetro / valor de retorno de una función, etc.

El rendimiento no es crítico, digamos, para una entrada de longitud total <100 caracteres, el resultado debe calcularse en <10 segundos en promedio de hardware moderno.

Python 2, 170 153/157/159

Acortado gracias a algunas de las ideas de Baptiste .

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)

El segundo salto de línea no es necesario.

Entrada: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Salida:SEDOLOREMAGNAD

Incluso con cadenas de entrada largas, esto se ejecuta en menos de 2 segundos si hay como máximo 7 cadenas de entrada (como es el caso en el ejemplo dado, que se ejecuta en 1.7 1.5 segundos en mi máquina). Sin embargo, con 8 o más cadenas de entrada, lleva más de 10 segundos, ya que la complejidad del tiempo es O(n!).

Como Baptiste señaló, range(99)debe reemplazarse range(len(w))si se deben admitir longitudes de entrada arbitrarias (lo que hace que la longitud total del código sea de 157 caracteres). Si se deben admitir cadenas de entrada vacías, debe cambiarse a range(len(w)+1). Sin range(99)embargo, creo que funciona correctamente para cualquier longitud de entrada total inferior a 200.

Más pruebas:

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

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

Mathematica 337 418 372

Después de intentar implementar sin éxito usando Mathematica's LongestCommonSubsequencePositions, recurrí a la coincidencia de patrones.

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]<>""]

La regla de coincidencia de patrones,

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

toma un par de palabras ordenadas (representadas como listas de caracteres) y devuelve: (1) las palabras, {a,y}y {y,b}seguido de (2) la subcadena común y, que vincula el final de una palabra con el comienzo de la otra palabra, y finalmente, la palabra combinada {a,y,b}que reemplazará las palabras de entrada. Ver Belisarius para un ejemplo relacionado: /mathematica/6144/looking-for-longest-common-substring-solution

Tres caracteres de subrayado consecutivos significan que el elemento es una secuencia de cero o más caracteres.

Reversese emplea más tarde para garantizar que ambas órdenes se prueben. Los pares que comparten letras enlazables se devuelven sin cambios e ignorados.

Editar :

Lo siguiente elimina de la lista las palabras que están "enterradas" (es decir, totalmente contenidas) en otra palabra (en respuesta al comentario de @ flornquake).

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

Ejemplo :

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

devoluciones

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

Uso

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

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

"LOREM"

{0.006256, "SEDOLOREMAGNAD"}

GolfScript, 66 caracteres

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

Bastante corto, pero debido a la complejidad de tiempo exponencial (y GolfScript) realmente lento, rompe el límite de tiempo de 10 segundos.

Ejemplos:

['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

Pitón 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)

Entrada: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Salida:SEDOLOREMAGNAD

Editar

Utilizando reducealgunos trucos de importación sucios, puedo reducir esto aún más (¡y solo a una línea!):

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)

Editar 2

Como notó flornquake, esto da resultados incorrectos cuando una palabra está contenida en otra. La solución para esto agrega otros 13 caracteres:

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)

Aquí está la versión limpiada:

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')

Es posible eliminar algunos caracteres a costa de la corrección teórica usando en range(99)lugar de range(len(x))(créditos para flornquake por pensar en este).

Python, 144 caracteres

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]

Stoma un conjunto de palabras Aque aún necesitan colocarse y una cadena que scontiene palabras colocadas hasta ahora. Escogemos una palabra restante ade Ay la superposición desde 0a len(a)personajes con el final de s.

Solo toma alrededor de 0.15 segundos en el ejemplo dado.

Haskell, 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 ""

Menos dos si la función no necesita estar vinculada a un nombre