Diberikan daftar string s_0, s_1, ..., s_nmenemukan string terpendek Syang berisi masing-masing s_0, s_1, ..., s_nsebagai substring .

Contoh :

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

Tulis program terpendek (atau fungsi) yang memecahkan masalah ini. Anda dapat mewakili string sebagai array atau daftar karakter / bilangan bulat jika Anda mau. Perpustakaan standar OK. Untuk input / output, Anda dapat menggunakan apa pun yang lebih nyaman: STDIN / STDOUT, prompt pengguna, nilai parameter / pengembalian fungsi dll.

Kinerja tidak kritis - katakanlah, untuk input dengan panjang total <100 karakter, hasilnya harus dihitung dalam <10 detik pada perangkat keras modern rata-rata.

Python 2, 170 153/157/159

Dipersingkat berkat beberapa ide 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)

Istirahat baris kedua tidak diperlukan.

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

Bahkan dengan string input panjang, ini berjalan dalam waktu kurang dari 2 detik jika ada paling banyak 7 string input (seperti halnya dalam contoh yang diberikan, yang berjalan dalam 1,7 1,5 detik pada mesin saya). Dengan 8 atau lebih input string, bagaimanapun, dibutuhkan lebih dari 10 detik, karena kompleksitas waktu O(n!).

Seperti yang ditunjukkan Baptiste, range(99)perlu diganti dengan range(len(w))jika panjang input yang sewenang-wenang harus didukung (membuat total panjang kode 157 karakter). Jika string input kosong harus didukung, itu harus diubah menjadi range(len(w)+1). Saya pikir range(99)bekerja dengan benar untuk setiap panjang input total kurang dari 200.

Tes lebih lanjut:

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

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

Mathematica 337 418 372

Setelah gagal mencoba menerapkan menggunakan Mathematica LongestCommonSubsequencePositions, saya beralih ke pencocokan pola.

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

Aturan pencocokan pola,

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

mengambil pasangan kata yang diurutkan (diwakili sebagai daftar karakter) dan mengembalikan: (1) kata-kata, {a,y}dan {y,b}diikuti oleh (2) substring yang umum y,, yang menghubungkan akhir satu kata dengan awal kata lain, dan, akhirnya, kata gabungan {a,y,b}itu akan menggantikan kata input. Lihat Belisarius untuk contoh terkait: /mathematica/6144/looking-for-longest-common-substring-sution

Tiga karakter garis bawah berturut-turut menandakan bahwa elemen tersebut adalah urutan dari nol atau lebih karakter.

Reversedigunakan kemudian untuk memastikan bahwa kedua pesanan diuji. Pasangan-pasangan yang berbagi surat-surat yang dapat ditautkan dikembalikan tidak berubah dan diabaikan.

Edit :

Berikut ini menghapus dari daftar kata-kata yang "dikubur" (yaitu sepenuhnya terkandung) dengan kata lain, (sebagai tanggapan terhadap komentar @ flornquake).

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

Contoh :

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

kembali

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

Pemakaian

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

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

"LOREM"

{0,006256, "SEDOLOREMAGNAD"}

GolfScript, 66 karakter

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

Cukup singkat, tetapi karena kompleksitas waktu yang eksponensial (dan GolfScript) benar-benar lambat, itu melanggar batas waktu 10 detik.

Contoh:

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

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

Edit

Menggunakan reducedan beberapa tipuan impor kotor, saya dapat mengurangi ini lebih jauh (dan hanya untuk satu baris!):

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

Seperti dicatat flornquake, ini memberikan hasil yang salah ketika satu kata terkandung dalam yang lain. Perbaikan untuk ini menambahkan 13 karakter lain:

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)

Inilah versi yang dibersihkan:

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

Dimungkinkan untuk mengurangi beberapa karakter dengan mengorbankan kebenaran teoretis dengan menggunakan range(99)alih-alih range(len(x))(kredit kepada korban karena memikirkan yang satu ini).

Python, 144 karakter

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]

SDibutuhkan satu set kata Ayang masih membutuhkan penempatan dan string sberisi kata-kata yang ditempatkan sejauh ini. Kami memilih kata yang tersisa adari Adan tumpang tindih dari 0ke len(a)karakter dengan akhir s.

Hanya memakan waktu sekitar 0,15 detik pada contoh yang diberikan.

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

Kurang dua jika fungsi tidak perlu terikat pada nama