Tantangan ini adalah tentang menulis kode untuk menyelesaikan masalah berikut.
Diberikan dua string A dan B, kode Anda harus menampilkan awal dan akhir indeks substring A dengan properti berikut.
- Substring A juga harus cocok dengan beberapa substring B dengan hingga satu subtitusi karakter tunggal dalam string.
- Seharusnya tidak ada lagi substring A yang memenuhi properti pertama.
Sebagai contoh:
A = xxxappleyyyyyyy
B = zapllezzz
Substring apple
dengan indeks 4 8
(pengindeksan dari 1) akan menjadi output yang valid.
Skor
Skor jawaban Anda akan menjadi jumlah panjang kode Anda dalam byte + waktu dalam detik di komputer saya saat dijalankan dengan string A dan B dengan panjang masing-masing 1 juta.
Pengujian dan input
Saya akan menjalankan kode Anda pada dua string dengan panjang 1 juta yang diambil dari string di http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/
Input akan pada standar masuk dan hanya akan menjadi dua string, dipisahkan oleh baris baru.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga open source dan tersedia secara bebas untuk Linux.
Mesin saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda. Sebagai konsekuensinya, hanya gunakan perangkat lunak gratis yang mudah tersedia dan harap sertakan instruksi lengkap cara menyusun dan menjalankan kode Anda.
sumber
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..
-- pikiran?appley
perlu dua pergantian pemain untuk mencocokkanapllez
. Mungkin Anda melewatkannyaapll
di B dan bukanappl
?Jawaban:
Waktu C ++: O (n ^ 2), ruang ekstra: O (1)
Dibutuhkan 0.2s untuk menyelesaikan data 15K pada mesin saya.
Untuk mengkompilasinya, gunakan:
Untuk menjalankannya, gunakan:
Penjelasan
Idenya sederhana, untuk string
s1
dans2
, kami mencoba mengimbangis2
dengani
:Saat offset 3:
Kemudian, untuk setiap offset
i
, kami melakukan pemindaian program dinamis padas1[i:]
dans2
. Untuk masing-masingj
, biarkanf[j, 0]
menjadi panjang maksimumd
sedemikian rupas1[j - d:j] == s2[j - i - d: j - i]
. Demikian pula, marif[j, 1]
menjadi panjang maksimumd
sedemikian sehingga strings1[j - d:j]
dans2[j - i - d:j - i]
berbeda paling banyak 1 karakter.Jadi untuk
s1[j] == s2[j - i]
, kami memiliki:Jika tidak:
Dan:
Karena kita hanya perlu f [j - 1,:] untuk menghitung f [j,:], hanya O (1) ruang ekstra yang digunakan.
Akhirnya, panjang maks adalah:
Kode
sumber
C ++
Saya mencoba memikirkan algoritma yang baik untuk melakukan ini, tapi saya agak terganggu hari ini dan tidak bisa memikirkan apa pun yang akan bekerja dengan baik. Ini berjalan pada waktu O (n ^ 3), jadi lambat sekali. Pilihan lain yang saya pikirkan bisa saja secara teori lebih cepat tetapi akan mengambil ruang O (n ^ 2), dan dengan input 1M, bahkan akan lebih buruk.
Memalukan, butuh 190 detik untuk input 15K. Saya akan mencoba memperbaikinya. Sunting: Menambahkan multiprocessing. Sekarang butuh 37 detik untuk input 15K pada 8 utas.
sumber
i < a.length()
menjadii < a.length - (longestA.second - longestA.first)
(sama untuk j dan b.length ()) karena Anda tidak perlu memproses kecocokan yang lebih kecil dari yang terpanjang saat iniR
Sepertinya saya terlalu memperumit masalah dengan solusi sebelumnya. Ini sekitar 50% lebih cepat (23 detik pada string 15k) dari yang sebelumnya dan cukup sederhana.
Ini tidak akan pernah menjadi pesaing karena bahasa, tetapi saya memang bersenang-senang melakukannya.
Tidak yakin dengan kerumitannya, tetapi lebih dari beberapa string ~ 15k dibutuhkan 43 detik menggunakan utas tunggal. Bagian terbesar dari itu adalah penyortiran array. Saya mencoba beberapa perpustakaan lain, tetapi tanpa perbaikan yang signifikan.
Metode:
sumber