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.
- Seharusnya tidak ada lagi substring A yang memenuhi properti pertama.
Sebagai contoh:
A = xxxappleyyyyyyy
B = zapplezzz
Substring apple
dengan indeks 4 8
(pengindeksan dari 1) akan menjadi output yang valid.
Fungsionalitas
Anda dapat berasumsi bahwa input akan sesuai standar atau dalam file di direktori lokal, itu adalah pilihan Anda. Format file hanya akan menjadi dua string, dipisahkan oleh baris baru. Jawabannya harus berupa program lengkap dan bukan hanya fungsi.
Saya akhirnya ingin menguji kode Anda pada dua substring yang diambil dari string di http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .
Skor
Ini adalah kode-golf dengan twist. Kode Anda harus dijalankan dalam O(n)
waktu, di mana n
total panjang input.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / interpreter / dll yang tersedia secara bebas. untuk Linux. Anda hanya harus menggunakan pustaka sumber terbuka standar yang tidak dirancang untuk menyelesaikan tugas ini. Jika terjadi perselisihan, saya akan menghitung ini sebagai pustaka mana pun yang datang sebagai standar dengan bahasa Anda atau yang dapat Anda instal di mesin ubuntu default dari repositori default.
Informasi berguna
Setidaknya ada dua cara untuk menyelesaikan masalah ini dalam waktu linier. Pertama adalah menghitung pohon sufiks pertama dan yang kedua adalah pertama menghitung array sufiks dan array LCP.
- Berikut ini penjelasan lengkap dan (mungkin berlebihan) dari konstruksi pohon sufiks waktu linear (ternyata beberapa gambarnya sayangnya kacau). Ada juga jawaban SO yang sangat bagus tentang konstruksi pohon akhiran waktu linear di https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english . Ini juga menyertakan tautan ke kode sumber. Penjelasan terperinci lainnya dapat ditemukan di sini , kali ini memberikan solusi lengkap dalam C.
- Bagian 2 dari http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf memberikan algoritme konstruksi susunan array akhiran waktu linear dan Lampiran A memiliki kode sumber C ++. Jawaban ini memberi tahu Anda bagaimana cara menghitung substring umum terpanjang https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays . Bagian 5 dari https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf yang juga memiliki ceramah video terkait https://courses.csail.mit.edu/6.851/spring12/lectures/L16 .html juga menjelaskan algoritma yang sama mulai pukul 1:16:00.
sumber
O(n) time
Apakah Anda yakin itu mungkin?Jawaban:
Python 2, 646 byte
Ini menggunakan algoritma miring yang dijelaskan dalam "Konstruksi Susunan Sufiks Kerja Linier Sederhana" oleh Kärkkäinen dan Sanders. Implementasi C ++ termasuk dalam makalah itu sudah terasa sedikit "golfy", tetapi masih ada banyak ruang untuk membuatnya lebih pendek. Sebagai contoh, kita bisa berulang sampai tiba pada array yang panjangnya satu, bukannya hubungan arus pendek seperti di kertas, tanpa melanggar
O(n)
persyaratan.Untuk bagian LCP, saya mengikuti "Komputasi Linear-Waktu Terpanjang-Umum-Awalan dalam Susunan Sufiks dan Aplikasinya" oleh Kusai et al.
Program mengeluarkan
1 0
jika substring umum terpanjang kosong.Berikut adalah beberapa kode pengembangan yang mencakup versi program yang lebih awal yang mengikuti implementasi C ++ sedikit lebih dekat, beberapa pendekatan yang lebih lambat untuk perbandingan, dan generator case uji sederhana:
sumber