Étant donné une liste de chaînes, s_0, s_1, ..., s_nrecherchez la chaîne la plus courte Squi contient chacune s_0, s_1, ..., s_ncomme sous - chaîne .

Exemples :

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

Écrivez le programme (ou la fonction) le plus court qui résout ce problème. Vous pouvez représenter des chaînes sous forme de tableaux ou de listes de caractères / entiers si vous le souhaitez. Les bibliothèques standard sont OK. Pour l'entrée / sortie, vous pouvez utiliser ce qui est plus pratique: STDIN / STDOUT, invite de l'utilisateur, paramètre / valeur de retour d'une fonction, etc.

Les performances ne sont pas critiques - disons, pour une entrée de longueur totale <100 caractères, le résultat doit être calculé en <10 secondes en moyenne sur un matériel moderne.

Python 2, 170 153/157/159

Raccourci grâce à certaines des idées 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)

Le deuxième saut de ligne n'est pas nécessaire.

Entrée: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Sortie:SEDOLOREMAGNAD

Même avec de longues chaînes d'entrée, cela s'exécute en moins de 2 secondes s'il y a au plus 7 chaînes d'entrée (comme c'est le cas dans l'exemple donné, qui s'exécute en 1,7 1,5 seconde sur ma machine). Avec 8 chaînes d'entrée ou plus, cependant, cela prend plus de 10 secondes, car la complexité temporelle est O(n!).

Comme l'a souligné Baptiste, range(99)doit être remplacé par range(len(w))si des longueurs d'entrée arbitraires doivent être prises en charge (ce qui fait la longueur totale du code 157 caractères). Si des chaînes d'entrée vides doivent être prises en charge, elles doivent être remplacées par range(len(w)+1). Je pense que range(99)fonctionne correctement pour toute longueur d'entrée totale inférieure à 200, cependant.

Plus de tests:

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

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

Mathematica 337 418 372

Après avoir essayé sans succès d'implémenter à l'aide de Mathematica LongestCommonSubsequencePositions, je me suis tourné vers la correspondance de modèles.

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 règle de correspondance de motifs,

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

prend une paire ordonnée de mots (représentés sous forme de listes de caractères) et renvoie: (1) les mots, {a,y}et {y,b}suivi par (2) la sous - chaîne commune, yqui relie l'extrémité d'un mot avec le début de l'autre mot, et, enfin, le mot combiné {a,y,b}qui remplacera les mots d'entrée. Voir Belisarius pour un exemple connexe: /mathematica/6144/looking-for-longest-common-substring-solution

Trois caractères de soulignement consécutifs signifient que l'élément est une séquence de zéro ou plusieurs caractères.

Reverseest utilisé plus tard pour garantir que les deux commandes sont testées. Les paires qui partagent des lettres pouvant être liées sont retournées inchangées et ignorées.

Modifier :

Ce qui suit supprime de la liste les mots qui sont "enterrés" (c'est-à-dire entièrement contenus) dans un autre mot (en réponse au commentaire de @ flornquake).

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

Exemple :

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

résultats

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

Usage

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

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

"LOREM"

{0,006256, "SEDOLOREMAGNAD"}

GolfScript, 66 caractères

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

Assez court, mais en raison de la complexité temporelle exponentielle (et GolfScript) très lent, il casse le délai de 10 secondes.

Exemples:

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

Entrée: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Sortie:SEDOLOREMAGNAD

modifier

À l'aide de reducequelques trucs importés, je peux réduire cela davantage (et à une seule ligne!):

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)

Modifier 2

Comme l'a noté le tremblement de terre, cela donne des résultats incorrects lorsqu'un mot est contenu dans un autre. La correction pour cela ajoute 13 autres caractères:

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)

Voici la version nettoyée:

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

Il est possible de raser quelques caractères au détriment de l'exactitude théorique en utilisant à la range(99)place de range(len(x))(crédits au tremblement de terre pour avoir pensé à celui-ci).

Python, 144 caractères

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]

Sprend un ensemble de mots Aqui doivent encore être placés et une chaîne scontenant des mots placés jusqu'à présent. Nous choisissons un mot restant ade Aet le chevauchons de 0à des len(a)caractères avec la fin de s.

Prend seulement environ 0,15 seconde sur l'exemple donné.

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

Moins deux si la fonction n'a pas besoin d'être liée à un nom