Shortest common superstring

Question

Given a list of strings s_0, s_1, ..., s_n find the shortest string S that contains each of s_0, s_1, ..., s_n as a substring.

Examples:

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

Write the shortest program (or function) that solves this problem. You can represent strings as arrays or lists of characters/integers if you want. Standard libraries are OK. For input/output you can use whatever is more convenient: STDIN/STDOUT, user prompt, parameter/return value of a function etc.

Performance is not critical - let's say, for an input of total length < 100 characters the result must be computed in < 10 second on average modern hardware.

Answer 1

Python 2, 170 153/157/159

Shortened thanks to some of Baptiste's ideas.

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)

The second line break is not needed.

Input: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Output: SEDOLOREMAGNAD

Even with long input strings, this runs in less than 2 seconds if there are at most 7 input strings (as is the case in the example given, which runs in 1.7 1.5 seconds on my machine). With 8 or more input strings, however, it takes more than 10 seconds, since the time complexity is O(n!).

As Baptiste pointed out, range(99) needs to be replaced with range(len(w)) if arbitrary input lengths should be supported (making the total length of the code 157 characters). If empty input strings should be supported, it has to be changed to range(len(w)+1). I think range(99) works correctly for any total input length less than 200, though.

More tests:

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

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

Answer 2

Mathematica 337 418 372

After trying unsuccessfully to implement using Mathematica's LongestCommonSubsequencePositions, I turned to pattern matching.

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

The pattern-matching rule,

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

takes an ordered pair of words (represented as lists of characters) and returns: (1) the words,{a,y} and {y,b} followed by (2) the common substring,y, that links the end of one word with the beginning of the other word, and, finally, the combined word {a,y,b} that will replace the input words. See Belisarius for a related example: https://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution

Three consecutive underscore characters signify that the element is a sequence of zero or more characters.

Reverse is employed later to ensure that both orders are tested. Those pairs that share linkable letters are returned unchanged and ignored.

Edit:

The following removes from the list words that are "buried" (i.e. fully contained) in another word, (in response to @flornquake's comment).

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

---

Example:

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

returns

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

Answer 3

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)

Input: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Output: SEDOLOREMAGNAD

Edit

Using reduce and some dirty import trickery, I can reduce this further (and to one line only!):

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)

Edit 2

As flornquake noted, this gives incorrect results when one word is contained in another. The fix for this adds another 13 chars:

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)

Here's the cleaned up version:

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

It's possible to shave off a few characters at the cost of theoretical correctness by using range(99) instead of range(len(x)) (credits to flornquake for thinking of this one).

Answer 4

Python, 144 chars

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 takes a set of words A that still need placing and a string s containing words placed so far. We pick a remaining word a from A and overlap it from 0 to len(a) characters with the end of s.

Takes only about 0.15 seconds on the given example.

Answer 5

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

Minus two if the function doesn't need to be bound to a name