Indeks Substring Terpendek

9

Saya orang yang malas tetapi efisien, karena banyak dari Anda mungkin juga. Jadi, setiap kali saya melakukan sesuatu, saya ingin melakukannya dengan sedikit usaha. Itulah sebabnya saya meminta Anda untuk menyelesaikan masalah ini untuk saya.

Apa yang saya miliki di sini adalah semacam dokumen. Pada setiap baris dokumen ini ada satu kata atau frase pendek. Dokumen tidak diurutkan, tapi tidak apa-apa saya tahu di mana semuanya berada. Saya dapat menggunakan beberapa bantuan menemukan hal-hal lebih cepat, dan untuk itu saya perlu daftar kedua. Di sinilah Anda masuk. Untuk setiap baris teks dalam dokumen ini, saya perlu pengenal. Sesuatu yang saya dapat CTRL+ F, tetapi tidak lebih dari mutlak diperlukan untuk mendapatkan satu hasil.

Input contoh:

(blank)
an apple
spiderman 3
7pm pick up laundry
tequila
fake mustache
dishes on wednesday
banana
biscuits
(blank)

Contoh output:

ap,3,7,q,f,w,ba,bi

Saya akan mengulangi lagi di sini, untuk memastikan kami berada di halaman yang sama:

  • Input adalah file teks yang tidak diformat yang berisi daftar item, dipisahkan oleh jeda baris. Saya memilikinya di sini dalam format .txt, itu disebut "STUFF.TXT"
  • Baris pertama dan terakhir dari dokumen kosong. Setiap baris lainnya berisi entri panjang> 0.
  • File hanya berisi karakter alfanumerik (semua huruf kecil), spasi, dan jeda baris.
  • Output yang diinginkan adalah daftar pengidentifikasi, dalam urutan yang sama dengan daftar asli saya.
  • Saya tidak ingin lebih dari satu kata pencarian untuk setiap item daftar. Jika ada beberapa jawaban, pilih satu, saya tidak peduli yang mana. Dalam contoh di atas saya memilih 'ap' untuk an apple, tetapi Anda bisa memilih 'n', 'a', 'pp', 'pl' atau 'le'. Bukan 'an', karena itu ada di banana.
  • Saya dapat meyakinkan Anda, file tidak pernah kosong, dan tidak pernah berisi duplikat.
  • Jika perlu , Anda dapat mencocokkan dengan terminator garis. Tapi itu pilihan terakhir hanya untuk digunakan ketika tidak ada cara lain untuk membedakan antara item daftar (misalnya 'apel' dan 'apel').

Tidak ada celah standar . Juga, ini kode golf sehingga kode terpendek menang.

Satu lagi contoh:

(blank)
ban
any
king
bean
yen
rake
raki
bar
(blank)

Dan hasilnya:

ban,ny,g,be,ye,ke,aki,ar
freekvd
sumber
1
@CarpetPython harus sesingkat mungkin. Spasi dapat berupa input dan output, menambahkannya ke pertanyaan.
freekvd
Bisakah kita juga menggunakan baris baru di awal istilah pencarian, jika satu string adalah sufiks dari yang lain?
Martin Ender
@ MartinBüttner ya. Itu sebabnya dokumen mulai dan berakhir dengan baris kosong, jadi Anda memiliki baris baru di awal dan akhir setiap item daftar.
freekvd
4
Saya cukup yakin masalah ini sudah selesai NP. Saya pikir saya bisa membuat pengurangan masalah sampul yang tepat untuk yang ini.
FUZxxl
4
Lebih dari itu Anda tidak akan melihat solusi kreatif karena tidak ada solusi yang lebih baik daripada brute force.
FUZxxl

Jawaban:

3

Pyth, 39 byte

Lsm.:bdtUbKfT.zj\,mhf!}Yjb-Kk+yky++bkbK

Bruteforces semua himpunan bagian dari setiap string dalam peningkatan panjang dan memeriksa apakah string itu terjadi di dalam yang lain Jika itu tidak berhasil, itu akan melakukan hal yang sama kecuali untuk semua himpunan bagian dari \nstring\n.

orlp
sumber
Saya mendapatkan kesalahan kombinasi jenis yang buruk ketika saya menguji ini. pyth.herokuapp.com/...
freekvd
@freekvd Heroku harus memiliki versi Pyth yang ketinggalan zaman, karena memanggil .:dengan string tipe pertama dan tipe kedua int bukanlah kesalahan. Coba gunakan Pyth dari repo: github.com/isaacg1/pyth
orlp