Shortest common superstring 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 &lt; 100 characters the result must be computed in &lt; 10 second on average modern hardware.
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: 

&gt;&gt;&gt; "AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"
SEDOLOREMAGNAD

&gt;&gt;&gt; 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 'abcdefghijklmnopqrstuvw
... xyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstu
... vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ZOOM', 'aZ', 'Za', 'ZA'
aZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZOOM