Kode Suburensi Umum terpanjang terpendek

11

Tugas Anda untuk memecahkan masalah SLCSC, yang terdiri dari menemukan kode sesingkat mungkin untuk menyelesaikan masalah Suburensi Umum Terpanjang .

Sebuah solusi yang valid untuk masalah LCS untuk dua atau lebih string S 1 , ... S n adalah string T panjang maksimal sehingga karakter dari T muncul di semua S i , dalam urutan yang sama seperti pada T .

Perhatikan bahwa T tidak harus menjadi sub string dari S i .

Contoh

Senar axbyczdan xaybzcmemiliki 8 urutan umum panjang 3:

abc abz ayc ayz xbc xbz xyc xyz

Semua ini akan menjadi solusi yang valid untuk masalah LCS.

Detail

Tulis program atau fungsi yang memecahkan masalah LCS, seperti dijelaskan di atas, mematuhi aturan berikut:

  • Input akan terdiri dari dua string atau lebih yang hanya berisi huruf kecil.

    Anda dapat membaca string tersebut sebagai array string atau string tunggal dengan pembatas pilihan Anda.

  • Kode Anda harus menampilkan salah satu dari solusi yang mungkin untuk masalah, secara opsional diikuti oleh umpan baris atau dikelilingi oleh tanda kutip.

  • Anda dapat mengasumsikan bahwa string lebih pendek dari 1000 karakter dan paling banyak 20 string.

    Dalam batas-batas ini, kode Anda harus berfungsi seperti yang diharapkan dalam teori (diberikan waktu dan memori tidak terbatas).

  • Kode Anda harus menyelesaikan kasus uji gabungan bagian berikutnya dalam waktu kurang dari satu jam di komputer saya (Intel Core i7-3770, 16 GiB RAM).

    Pendekatan yang hanya mengulangi semua kemungkinan berikutnya tidak akan memenuhi batas waktu.

  • Menggunakan bawaan yang meremehkan tugas ini, seperti LongestCommonSequence, tidak diizinkan.

Aturan standar berlaku.

Uji kasus

a
ab

Keluaran: a


aaaaxbbbb
bbbbxcccc
ccccxaaaa

Keluaran: x


hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl

Output: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrlatau urutan umum lainnya dengan panjang yang sama


riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg

Output: icsvllvjnlktywuaratau urutan umum lainnya dengan panjang yang sama


rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr

Output: krkkatau urutan umum lainnya dengan panjang yang sama


bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja

Output: codeatau urutan umum lainnya dengan panjang yang sama


nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt

Output: golfatau urutan umum lainnya dengan panjang yang sama


epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp

Output: string kosong

Dennis
sumber
menipu? codegolf.stackexchange.com/questions/20427/…
Bukan berarti Charles
@NotthatCharles Tidak semua. Pertanyaan itu hanya memberikan dua string sebagai input dan tidak memiliki batas waktu. Semua jawaban yang ada menggunakan pendekatan naif yang besarnya terlalu lambat untuk mematuhi aturan pertanyaan ini.
Dennis
Contoh terakhir mungkin membutuhkan waktu paling lama untuk dikomputasi, namun dengan terlebih dahulu menghapus setiap karakter yang tidak muncul di setiap string itu sepele untuk menghasilkan string kosong. Bisakah Anda menambahkan contoh lain dengan jumlah string dan panjang string yang sama, di mana setiap karakter yang digunakan muncul di setiap string dan di mana LCS setidaknya 5 karakter atau lebih? Sesuatu seperti: ghostbin.com/paste/x9caq
Tyilo
@Tylio Menggabungkan beberapa logika yang mengakhiri rekursi lebih awal jika string tidak memiliki karakter yang lebih umum cukup banyak tentang kasus uji terakhir.
Dennis
@ Dennis Jadi solusinya seharusnya tidak dapat berjalan dalam waktu yang wajar dengan 20 string 1000 sewenang-wenang?
Tyilo

Jawaban:

4

CJam, 31

q~L{_:&\f{_2$f#:).>j+}{,}$W>s}j

Cobalah online

9 byte golf berkat Dennis!

Penjelasan:

Algoritma ini mencoba setiap karakter yang mungkin untuk posisi pertama selanjutnya, mengganti setiap string dengan substring setelah kemunculan pertama karakter itu, dan kemudian menyebut dirinya secara rekursif (dengan memoisasi).

q~          read and evaluate the input (taken as an array)
L{…}j       execute block with recursive memoization and no starting values
  _         duplicate the array of strings
  :&\       intersect the strings as character sets and move before the array
             these are all the possible characters for the sequence
  f{…}      for each character and the array
    _2$     duplicate the array and the character
    f#      find the character position in each string
    :)      increment the positions (to skip the character)
    .>      slice each string starting at the corresponding position
    j       call the j block recursively
    +       concatenate the starting character with the result
  {,}$      sort resulting strings (one for each character) by length
  W>        keep only the last element, if any
  s         convert (from 0/1-string array) to string
aditsu berhenti karena SE adalah JAHAT
sumber
5

Python - 665 644

Tingkat lekukan:

1: space
2: tab
3: tab + space
4: 2 tabs
5: 2 tabs + space

Kode mendefinisikan fungsi o, yang mengambil daftar string sebagai argumen dan mengembalikan salah satu LCS untuk string.

def o(t):
 t=[[y for y in x if y in reduce(lambda x,y:x.intersection(y),t,set(t[0]))]for x in t];l=map(len,t);C=[0]*reduce(lambda x,y:x*-~y,l,1);y=lambda z:[x-1for x in z];m=len(t);e=enumerate
 def g(h):
    r,x=0,1
    for k,j in e(h):r+=-~j*x;x*=-~l[k]
    return r
 def f(h):
    i=len(h)
    if i==m:
     b=g(h);c=t[0][h[0]]
     for k,j in e(h):
         if t[k][j]!=c:break
     else:C[b]=1+C[g(y(h))];return
     r=0
     for k,_ in e(h):a=h[:];a[k]-=1;r=max(r,C[g(a)])
     C[b]=r;return
    for j,_ in e(t[i]):f(h+[j])
 def p(h):
    if min(h)==-1:return''
    v=C[g(h)]
    for k,_ in e(h):
        a=h[:];a[k]-=1
        if v==C[g(a)]:return p(a)
    return p(y(h))+t[0][h[0]]
 f([]);return p(y(l))

Kode uji:

tests = [
"""
a
ab
""",
"""
aaaaxbbbb
bbbbxcccc
ccccxaaaa
""",
"""
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
""",
"""
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
""",
"""
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
""",
"""
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
""",
"""
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
""",
"""
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
"""
]

for s in tests:
 print o(s.strip().split())

Waktu yang diperlukan untuk menjalankan tes di komputer saya:

$ time python 52808-shortest-longest-common-subsequence-code-golfed.py
a
x
hecbpyhogntqtpcqgkxchpsieuhbncvhuqndbjqmclchqyfhtdvgoysuhrrl
icsvllvanlktywuar
krkk
code
golf

        9.03 real         8.99 user         0.03 sys
Tyilo
sumber
1
Anda harus menambahkan byte untuk mendapatkan kode Anda menjadi 666 byte. Jadi logam. \ m /
Alex A.
@AlexA. Ya saya juga memperhatikan bahwa ketika menghitung byte seperti itu termasuk baris baru pada baris terakhir.
Tyilo
Ada beberapa perbaikan kecil yang saya lihat segera yang seharusnya membantu. Pertama, di mana pun Anda memiliki (n+1), Anda dapat menggantinya dengan -~nuntuk menyimpan 2 byte dalam setiap kasus. Juga, di mana saja Anda menggunakan mapdengan lambda, pertimbangkan menggunakan pemahaman daftar sebagai gantinya. Misalnya, map(lambda x:x-1,z)dapat dipersingkat tiga byte dengan mengubahnya menjadi [~-x for x in z].
Kade
r,x=r+(j+1)*x,x*(l[k]+1)dapat disingkat menjadi r+=(j+1)*x;x*=(l[k]+1). Juga, Anda tidak perlu u=...karena uhanya digunakan di satu tempat. Ganti saja kode itu dengan surat itu u.
mbomb007
@ Vioz- dan mbomb007 Terima kasih.
Tyilo
4

Pyth, 59 58 55 35 byte

L&@Fb?+yPMbeeb@FeMbeolNmyXJbdP@bdlb

Potong 20 byte kekalahan berkat @isaacg!

Versi 55 byte:

DCHR?k!&.AH@FH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Potong 3 byte dengan mengubah .U@bZke @F(operator lipat).

Versi 58 byte:

DCHR?k!&.AH.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Potong byte dengan mengubah format kondisional boolean.

Versi 59 byte:

DCHR?k|!.AH!.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Ini sulit! Python terus melakukan segmentasi! Cukup yakin itu semacam bug, tapi saya tidak bisa mendapatkan test case minimal. Baiklah.

Saya mendasarkan algoritma dari yang satu ini . Yang baik-baik saja, kecuali bahwa yang dirancang hanya untuk dua string. Saya harus men-tweak sedikit untuk membuatnya bekerja lebih banyak. Kemudian, test case terakhir terlalu lama, jadi saya harus menambahkan cek tambahan untuk keluar dari rekursi jika tidak ada karakter yang lebih umum.

Ini cukup lambat, tetapi harus memakan waktu kurang dari satu jam (semoga). Saya sedang menguji Core i3 saya dengan 6 GB RAM, jadi Core i7 16-GB Anda harus menerobos ini. :)

Saya juga memanfaatkan fungsi memo-otomatis Pyth untuk membuatnya sedikit lebih cepat.

EDIT : @Dennis bilang sudah lewat!

Untuk mengujinya, tambahkan baris berikut:

CQ

dan berikan daftar string melalui input standar (misalnya ['a', 'ab']).

Penjelasan untuk versi 35 byte:

WIP.

Penjelasan untuk versi 55 byte:

DCH                                                        define a function C that takes a list of strings H
   R                                                       return the following expression
    ?                                                      if
      !&.AH@FH                                             there are no more common letters OR all the strings are empty
     k                                                     return the empty string
              ?          ql{medH1                          else if the last character of every string is equal
               +Cm<1dHeeH                                  return the result of adding the last character to recursion with every item without its last character
                                 h.MlZ.eC++<Hk]<1b>HhkH    otherwise, return the largest result of recursing len(H) times, each time with one element's last character cut off
kirbyfan64sos
sumber
@ Dennis Ok; Saya akan mengerjakannya.
kirbyfan64sos
@Dennis Diperbarui. Anda bisa coba lagi sekarang.
kirbyfan64sos
Test case terakhir selesai secara instan sekarang.
Dennis
@Dennis YESSSSS !!
kirbyfan64sos
@ kirbyfan64sos Tentang Segfaults: Segfault Pyth ketika kedalaman rekursi terlalu tinggi, seperti pada rekursi tak terbatas.
isaacg
4

C, 618 564 byte

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y=n-1,z,i,t,m=0,w=1;for(;y;)x[y--]=999;for(;y<N;y++){for(i=0;i<n&&s[i]==R[y][i];i++);if(i/n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)t&=!!*j[i];y&=j[i]-s[i]>x[i]?z=0,1:0;}t&=!y;I:if(t){if(z)for(i=0;i<n;i++)x[i]=j[i]-s[i];d++,t+=L(j,n),d--,m=t>m?a=c,t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Dan di sini terurai, untuk "keterbacaan":

d,M,N,A[9999][2];
char*(R[9999][20]),b[1000];
L(char**s,n){
    char*j[20],c,a=0;
    int x[n],y=n-1,z,i,t,m=0,w=1;
    for(;y;)
        x[y--]=999;
    for(;y<N;y++){
        for(i=0;i<n&&s[i]==R[y][i];i++);
        if(i/n){
            a=A[y][0];
            m=A[y][1];
            w=0;
            if(m+d<M||!a)
                goto J;
            else{
                c=a;
                goto K;
            }
        }
    }
    for(c=97;w&&c<'{';c++){
        K:
        t=1,
        y=1,
        z=1;
        for(i=0;i<n;j[i++]++){
            for(j[i]=s[i];*j[i]-c;j[i]++)
                t&=!!*j[i];
            y&=j[i]-s[i]>x[i]?z=0,1:0;
        }
        t&=!y;
        I:
        if(t){
            if(z)
                for(i=0;i<n;i++)
                    x[i]=j[i]-s[i];
            d++,
            t+=L(j,n),
            d--,
            m=t>m?a=c,t:m;
        }
    }
    if(w){
        for(y=0;y<n;y++)R[N][y]=s[y];
        A[N][0]=a;
        A[N++][1]=m;
    }
    J:
    if(d+m>=M)
        M=d+m,b[d]=a;
    if(!d)
        N=0,M=0,puts(b);
    return m;
}

Hadirin sekalian, saya telah melakukan kesalahan yang mengerikan. Itu digunakan untuk menjadi cantik ... Dan goto-kurang ... Setidaknya sekarang itu cepat .

Kami mendefinisikan fungsi rekursif L yang mengambil input array sarray karakter dan jumlah nstring. Fungsi mengeluarkan string yang dihasilkan ke stdout, dan secara tidak sengaja mengembalikan ukuran karakter string itu.

Pendekatan

Meskipun kodenya berbelit-belit, strategi di sini tidak terlalu rumit. Kita mulai dengan algoritma rekursif yang agak naif, yang akan saya uraikan dengan pseudocode:

Function L (array of strings s, number of strings n), returns length:

Create array of strings j of size n;

For each character c in "a-z",
    For each integer i less than n,
         Set the i'th string of j to the i'th string of s, starting at the first appearance of c in s[i]. (e.g. j[i][0] == c)
         If c does not occur in the i'th string of s, continue on to the next c.
    end For

    new_length := L( j, n ) + 1; // (C) t = new_length
    if new_length > best_length
        best_character := c; // (C) a = best_character
        best_length := new_length; // (C) m = best_length
    end if
end For

// (C) d = current_depth_in_recursion_tree
if best_length + current_depth_in_recursion_tree >= best_found
     prepend best_character to output_string // (C) b = output_string
     // (C) M = best_found, which represents the longest common substring found at any given point in the execution.
     best_found = best_length + current_depth;
end if

if current_depth_in_recursion_tree == 0
    reset all variables, print output_string
end if 

return best_length

Sekarang, algoritma ini sendiri cukup mengerikan (tapi bisa muat sekitar ~ 230 byte, saya temukan). Ini bukan bagaimana seseorang mendapatkan hasil yang cepat. Algoritma ini berskala sangat buruk dengan panjang string. Algoritma ini , bagaimanapun, skala cukup baik dengan jumlah string yang lebih besar. Kasing terakhir akan dipecahkan secara instan, karena tidak ada string yang smemiliki karakter yang csama. Ada dua trik utama yang saya terapkan di atas yang menghasilkan peningkatan kecepatan luar biasa:

  • Di setiap panggilan L, periksa apakah kami telah diberi input yang sama sebelumnya. Karena dalam praktiknya informasi diteruskan melalui pointer ke set string yang sama, kita tidak benar - benar harus membandingkan string, hanya lokasi, yang bagus. Jika kami menemukan bahwa kami telah mendapatkan informasi ini sebelumnya, tidak perlu menjalankan perhitungan (sebagian besar waktu, tetapi mendapatkan output membuat ini sedikit lebih rumit) dan kami bisa lolos hanya dengan mengembalikan panjangnya. Jika kami tidak menemukan kecocokan, simpan rangkaian input / output ini untuk dibandingkan dengan panggilan berikutnya. Dalam kode C, forloop kedua mencoba menemukan kecocokan dengan input. Pointer input yang diketahui disimpan R, dan nilai output karakter dan panjang yang sesuai disimpanA. Paket ini memiliki efek drastis pada runtime, terutama dengan string yang lebih panjang.

  • Setiap kali kita menemukan lokasi dari cdalam s, ada kesempatan kita tahu langsung dari kelelawar bahwa apa yang kita temukan adalah tidak optimal. Jika setiap lokasi cmuncul setelah beberapa lokasi diketahui dari surat lain, kami secara otomatis tahu bahwa ini ctidak mengarah ke substring yang optimal, karena Anda dapat memasukkan satu huruf lagi di dalamnya. Ini berarti bahwa untuk biaya yang kecil, kami berpotensi menghapus beberapa ratus panggilan Luntuk string besar. Dalam kode C di atas, yadalah set bendera jika kita secara otomatis tahu bahwa karakter ini mengarah ke string suboptimal, danz merupakan set bendera jika kita menemukan karakter yang secara eksklusif memiliki penampilan lebih awal daripada karakter lain yang dikenal. Penampilan karakter paling awal saat ini disimpan dix. Implementasi saat ini dari ide ini agak berantakan, tetapi kinerja hampir dua kali lipat dalam banyak hal.

Dengan dua ide ini, apa yang tidak selesai dalam satu jam sekarang membutuhkan waktu sekitar 0,015 detik.

Mungkin ada banyak trik kecil yang dapat mempercepat kinerja, tetapi pada titik ini saya mulai khawatir tentang kemampuan saya untuk bermain golf semuanya. Saya masih belum puas dengan golf, jadi saya akan kembali lagi nanti!

Pengaturan waktu

Inilah beberapa kode pengujian, yang saya undang untuk Anda coba secara online :

#include "stdio.h"
#include "time.h"

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int main(int argc, char** argv) {
    /* Our test case */
    char* test7[] = {
        "nqrualgoedlf",
        "jgqorzglfnpa",
        "fgttvnogldfx",
        "pgostsulyfug",
        "sgnhoyjlnfvr",
        "wdttgkolfkbt"
    };

    printf("Test 7:\n\t");
    clock_t start = clock();

    /* The call to L */
    int size = L(test7, SIZE_ARRAY(test7));


    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("\tSize: %d\n", size);
    printf("\tElapsed time: %lf s\n", dt);

    return 0;
}

Saya menjalankan test case OP pada laptop yang dilengkapi dengan chip Intel Core i7 1,7 GHz, dengan pengaturan optimalisasi -Ofast. Simulasi melaporkan puncak 712KB diperlukan. Berikut ini contoh proses dari setiap kasus uji, dengan timing:

Test 1:
    a
    Size: 1
    Elapsed time: 0.000020 s
Test 2:
    x
    Size: 1
    Elapsed time: 0.000017 s
Test 3:
    hecbpyhogntqppcqgkxchpsieuhbmcbhuqdjbrqmclchqyfhtdvdoysuhrrl
    Size: 60
    Elapsed time: 0.054547 s
Test 4:
    ihicvaoodsnktkrar
    Size: 17
    Elapsed time: 0.007459 s
Test 5:
    krkk
    Size: 4
    Elapsed time: 0.000051 s
Test 6:
    code
    Size: 4
    Elapsed time: 0.000045 s
Test 7:
    golf
    Size: 4
    Elapsed time: 0.000040 s
Test 8:

    Size: 0
    Elapsed time: 0.000029 s


Total time: 0.062293 s

Dalam bermain golf, saya mencapai performa yang cukup signifikan, dan karena orang-orang sepertinya menyukai kecepatan kasar (0,013624 detik untuk menyelesaikan semua test case digabungkan) dari solusi 618-byte saya sebelumnya, saya akan meninggalkannya di sini untuk referensi:

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y,z,i,t,m=0,w=1;for(y=0;y<n;y++)x[y]=999;for(y=0;y<N;y++){for(i=0;i<n;i++)if(s[i]!=R[y][i])break;if(i==n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)if(!*j[i]){t=0;goto I;}if(j[i]-s[i]>x[i])z=0;if(j[i]-s[i]<x[i])y=0;}if(y){t=0;}I:if(t){if(z){for(i=0;i<n;i++){x[i]=j[i]-s[i];}}d++,t+=L(j,n),d--,m=t>m?(a=c),t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Algoritme itu sendiri tidak berubah, tetapi kode baru bergantung pada divisi dan beberapa operasi bitwise rumit yang akhirnya memperlambat semuanya.

BrainSteel
sumber
Saya sedang berpikir tentang memposting tantangan kode tercepat tentang topik yang serupa, tetapi sepertinya saya tidak perlu lagi. 0,01 dan 712KB sangat mencengangkan.
Dennis
Ini luar biasa!
kirbyfan64sos
Melihat penjelasan Anda, apa-apaan ini best_found? Itu hanya disebutkan dua kali, satu kali ketika digunakan dalam kondisi, dan yang lainnya ketika diatur ulang.
kirbyfan64sos
Melihat ke sumber C, tampaknya best_founddiatur ke best_length + current_depth. Anda mungkin harus menyebutkan itu dalam penjelasannya!
kirbyfan64sos
@ kirbyfan64sos best_foundadalah bilangan bulat global yang menjelaskan panjang substring umum terpanjang yang ditemukan pada titik tertentu dalam eksekusi. Saya akan menjelaskannya!
BrainSteel
1

Python 2, 285

Kode:

import re
def f(s,a,b):
  if b==[]:return s+f('',[],a)
  if a==[]:return s+max([f(b[0][i],[b[0][i+1:]],b[1:]) for i in range(len(b[0]))],key=len) if b[0]!='' else ''
  return max([f(s,a+[b[0][i.start()+1:]],b[1:]) for i in re.finditer(s[-1],b[0])],key=len) if ~b[0].find(s[-1]) else ''

Pemakaian:

print f('',[],['axbycz','xaybzc'])

Penjelasan:

Ini adalah fungsi rekursif. sadalah karakter yang kami cari. aberisi daftar string yang diiris setelahnya s. bmengandung daftar string yang belum pernah ditemukan. fmengembalikan string umum terpanjang.

Kondisi pertama memeriksa apakah kami sudah selesai melewati semua string. jika demikian, artinya sadalah karakter yang umum, dan ia kembali sdan mencari karakter yang lebih umum.

Kondisi kedua memeriksa jika kita tidak mulai melalui string apa pun, artinya kita bahkan tidak memiliki karakter ( a==[]sama dengan s==''). jika demikian kita periksa setiap karakter dari string pertama di b.

Baris terakhir memindahkan string pertama bke a, dengan menemukan setiap kemunculan sdi string ini.

Pada panggilan pertama, sharus string kosong. aharus daftar kosong dan bharus berisi semua string.

TheCrypt
sumber
2
Anda harus menggunakan argumen default sehingga hanya string yang perlu disediakan untuk fungsi, seperti f(b,s='',a=[]).
feersum