Latar Belakang
Insiden adalah bahasa pemrograman yang cukup tidak biasa, karena daftar tokennya tidak ditentukan sebelumnya, melainkan disimpulkan dari input. Dengan demikian, melakukan token program Insiden bisa sangat sulit, terutama jika Anda ingin melakukannya secara efisien. Tugas ini adalah tentang melakukan itu sendiri.
Tugas
Program Anda akan diberikan string sebagai input. Berikut adalah algoritma yang digunakan Insiden untuk Tokenise:
- Identifikasi semua string yang terjadi sebagai substring input dengan tepat tiga cara (yaitu ada tepat tiga kemunculan string dalam input).
- Buang salah satu string yang merupakan substring dari string lain (misalnya untuk input
ababab
, satu-satunya string yang tersisa adalahab
, bukana
ataub
, karenaa
danb
keduanya merupakan substring dariab
). - Buang string apa pun yang tumpang tindih dalam input. (Misalnya,
aaaa
berisi tepat tiga salinanaa
, tetapi salinan ini tumpang tindih pada karakter kedua dan ketiga, sehingga akan dibuang. Demikian juga, dalamabababa
, ada tiga salinanab
dan tiga salinanba
, tetapi karakter kedua hingga keenam masing-masing pada tumpang tindih dari aab
dan aba
, sehingga keduanyaab
danba
akan dibuang). - Setiap string yang tersisa pada titik ini adalah token yang digunakan oleh program. Tokenis input asli ke dalam urutan token ini (karena membuang di langkah sebelumnya, hanya akan ada satu cara untuk melakukannya). Setiap karakter dalam input yang bukan bagian dari token apa pun diperlakukan sebagai komentar dan dibuang.
Program Anda harus mengambil string sebagai input, dan mengembalikan tokenation yang sesuai dari string (daftar token, yang masing-masing dinyatakan sebagai string) sebagai output. Selain itu, ini harus dilakukan setidaknya dengan cukup efisien; khususnya, program harus dijalankan dalam waktu kuadratik ("O (n²)") atau lebih baik. (Kebetulan, hampir pasti mungkin lebih cepat daripada kuadrat, tetapi ini bukan algoritma tercepat , jadi silakan gunakan algoritma tersest yang dapat Anda temukan yang sesuai dengan batasan kompleksitas.)
Klarifikasi
- Meskipun secara teori program-program Insiden dapat memuat salah satu dari 256 oktet, dapat diterima untuk tujuan tantangan ini bagi program Anda untuk hanya menangani input yang terbentuk dari ASCII yang dapat dicetak (termasuk ruang), ditambah baris dan tab baru. (Semua program Insiden yang diketahui membatasi diri pada bagian ini). Perhatikan bahwa spasi / baris baru / tab tidak spesial dan dapat muncul di tengah-tengah token; Insiden memperlakukan semua 256 oktet sebagai buram.
- Definisi "kuadrat waktu" adalah "jika ukuran input digandakan, program akan berjalan lebih lambat dengan tidak lebih dari konstanta ditambah faktor 4", yaitu jika t ( x ) adalah waktu maksimum yang diperlukan program Anda untuk proses input ukuran x , maka harus ada beberapa konstanta k sehingga t (2 x ) <4 t ( x ) + k untuk semua x . Ingatlah bahwa membandingkan string membutuhkan waktu sebanding dengan panjang string.
- Program Anda secara teoritis harus dapat menangani program input dengan panjang berapa pun jika dijalankan dalam varian (kemungkinan hipotetis) dari bahasa Anda yang memiliki memori tidak terbatas dan menggunakan bilangan bulat tak terbatas (tidak apa-apa jika program gagal mencapai tujuan ini ketika dijalankan dalam praktik karena bilangan bulat bahasa atau memori sebenarnya menjadi sangat besar). Anda dapat mengasumsikan (untuk tujuan penghitungan kompleksitas) bahwa bilangan bulat yang tidak lebih besar dari panjang input dapat dibandingkan dalam waktu konstan (walaupun perlu diingat bahwa jika Anda menggunakan nilai yang lebih besar, misalnya karena mengubah input menjadi bilangan bulat tunggal, mereka akan membutuhkan waktu lama untuk membandingkan sebanding dengan jumlah digit yang mereka miliki).
- Anda dapat menggunakan algoritma apa pun yang sesuai dengan batasan kompleksitas, meskipun itu tidak mengikuti langkah yang sama seperti algoritma yang diposting di atas, asalkan menghasilkan hasil yang sama.
- Teka-teki ini adalah tentang token input, bukan benar-benar memformat output. Jika cara paling alami untuk menampilkan daftar dalam bahasa Anda melibatkan format yang ambigu (mis. Dipisahkan baris ketika string berisi baris baru literal, atau tanpa pembatas di antara string), jangan khawatir tentang fakta bahwa output berakhir ambigu ( selama daftar sebenarnya dibangun). Anda mungkin ingin membuat versi kedua kiriman Anda yang menghasilkan output yang jelas, untuk membantu dalam pengujian, tetapi versi asli adalah versi yang menghitung untuk penilaian.
Kasus cobaan
Untuk string input berikut:
aaabcbcbcdefdfefedghijghighjkllkklmmmmonono-nonppqpq-pqprsrsrstststuvuvu
program Anda harus menghasilkan daftar keluaran berikut:
a a a bc bc bc d e f d f e f e d gh gh gh k l l k k l pq pq pq u u u
Kondisi kemenangan
Ini adalah kode-golf , sehingga program yang paling pendek valid (yaitu perilaku input / output yang benar dan cukup cepat untuk dijalankan), diukur dalam byte, menang.
Jawaban:
C (gcc), 324 byte
Fungsi ini
f
mengambil string yang diakhiri dengan nol dan mencetak token ke stdout. Semua baris baru dapat dihapus dari kode di bawah ini.Versi 376 byte yang lebih lama ini sedikit lebih mudah dibaca; penjelasan di bawah ini berlaku untuk itu.
k(0)
menghasilkan tabelt
untuk polap
untuk algoritma Knuth – Morris – Pratt.K(c)
proses karakter berikutnyac
dari string pencarian dan pembaruanm
, panjang awalan terbesarp
yang dapat ditemukan berakhir pada karakter yang paling baru diproses.Di
for
loop pertama , untuk setiap indeksa
dalam string, kami menghitung berapa kali setiap nilai yang mungkinm
terjadi saat mencari di seluruh string untuk mulai substring dia
. Kemudian kita mencari yang terbesarl
sehingga panjang-l
mulai substringa
terjadi tepat 3 kali. Jika cukup pendek untuk sepenuhnya berisi string yang ditemukan sebelumnyaa
, kami mengabaikannya. Jika tumpang tindih, kami menghapus string sebelumnya dariz
, array merekam token mana yang akan disimpan. Kalau tidak, panjangnya disimpan diz
.Kemudian, kami menggunakan KMP lagi untuk mencari string untuk token yang direkam
z
. Jika salah satunya ditemukan di lokasi dengan entri 0z
, kita tahu bahwa token ini dihapus karena tumpang tindih. Jika token tidak dihapus, itu dicetak.sumber
O(n^2)
atau lebih cepat. Dan mengapa ada!!
di sana!!z[x-m]
?*Z
adalah panjang token berikutnya yang perlu menjadi 0 jika salah satu kejadian token lainnya memiliki nilai 0 pada indeks mereka dalam array, atau menyimpan nilai yang sama jika tidak (dalam hal ini!!z[x-m]
harus 1.!!
itu ada di sana.!!x
harus tetapx
, atau apakah itu memunculkan trik yang tidak saya ketahui?!!x
membuatx
boolean mewakili "kebenarannya". Jadi,!!1 == true
dan!!0 == false
. Saya tidak tahu C secara khusus, tapi begitulah biasanyaJavaScript,
878867842825775752717712704673664650641 byteBerkat @Kritixi Lithos untuk membantu golf kode
Terima kasih kepada @ User2428118 untuk bermain golf 14 byte
(Tidak akan berfungsi di IE7) (Baris baru harus dimasukkan sebagai "
\n
" dan tab sebagai "\t
" dalam string input, karakter unicode apa pun harus dimasukkan sebagai\u####
)Cobalah secara Online
Penjelasan tentang cara kerjanya dan kode ungolfed
Pertama, program ini menghasilkan array Knuth Morris Pratt untuk setiap substring yang memungkinkan;
Selanjutnya, program menemukan panjang pencocokan maksimum pada setiap indeks tunggal dalam kata dengan setiap substring. (ini saatnya O (n ^ 2))
Program ini menggunakan data ini untuk menemukan substring terpanjang yang muncul tiga kali untuk setiap karakter awal dalam string.
Program ini menggunakan data ini untuk menghilangkan semua substring yang tidak muncul tepat tiga kali dan semua substring dari substring yang paling lama berlaku.
Selanjutnya, program mengatur semua substring yang tumpang tindih atau sebagian untuk dihapus.
Untuk setiap nilai yang akan dihapus, semua substring yang setara juga dihapus.
Akhirnya, program bergabung dengan array substring bersama dan mengeluarkannya.
sumber
while
danif
blok yang hanya memiliki 1 pernyataan di dalamnya. Anda dapat menghapus kawat gigi di{}
sekitar pernyataan itu. Misalnya,if(word.charAt(index+i)==word.charAt(index+j)){j++;}
dapat menjadiif(word.charAt(index+i)==word.charAt(index+j))j++;
&&
s untuk menggantiif
pernyataan, saya memindahkan pernyataan dalam loop sehingga mereka akan berakhir dengan satu pernyataan di bawahnya sehingga saya bisa menghapus kawat gigi. Saya menggunakan terner untuk menggantikan beberapa pernyataan if. Saya memindahkan barang-barang dan berakhir pada 946 byte . Jika Anda tidak mengerti sesuatu yang saya lakukan, jangan ragu untuk bertanya kepada saya :)