Tugas
Tugasnya adalah bermain golf algoritma pencocokan string tepat waktu pilihan Anda.
Memasukkan
Dua baris teks disediakan pada input standar, dipisahkan oleh baris baru. Baris pertama berisi "pola" dan hanya akan menjadi string ASCII yang diambil dari surat-surat a-z
.
Baris kedua berisi "teks" yang lebih panjang dan juga akan berupa string ASCII yang diambil dari surat-surat a-z
.
Keluaran
Daftar indeks di mana pencocokan tepat terjadi. Anda harus menampilkan posisi awal setiap pertandingan yang terjadi.
Spesifikasi
Algoritme Anda dapat menghabiskan waktu linear untuk memproses ulang pola. Kemudian harus membaca teks dari kiri ke kanan dan mengambil waktu konstan untuk setiap karakter tunggal dalam teks dan output setiap kecocokan baru segera setelah itu terjadi. Pertandingan tentu saja bisa saling tumpang tindih.
Algoritma
Ada banyak algoritma pencocokan tepat waktu. Satu disebutkan di wiki untuk KMP misalnya. Anda dapat menggunakan salah satu yang Anda suka tetapi Anda harus selalu menampilkan jawaban yang benar.
Saya akan membuat tabel per pemimpin bahasa sehingga mereka yang lebih suka bahasa populer juga bisa menang dengan cara mereka sendiri. Tolong jelaskan algoritma mana yang telah Anda terapkan.
Waktu sebenarnya
Tampaknya ada banyak kebingungan tentang apa yang dimaksud dengan real-time. Itu tidak hanya berarti waktu linier. Jadi standar KMP tidak real-time. Tautan dalam pertanyaan secara eksplisit menunjuk ke bagian halaman wiki untuk KMP tentang varian real-time KMP. Boyer-Moore-Galil juga tidak real-time. Ini cstheory pertanyaan / jawaban membahas masalah ini atau satu hanya bisa google "real-time yang sebenarnya cocok" atau istilah serupa.
sumber
abcd
danacbdefg
, saya akan menampilkan1 4
, untuka
dand
?a
dand
cocok. Adaabcd
danacbdefg
, dana
dand
berada pada posisi yang identik.Jawaban:
Python 2, 495 byte
Yang ini adalah KMP real-time, yang jauh lebih pendek dan hanya sedikit lebih lambat daripada algoritma BMG (yang biasanya sublinear). Panggil dengan
K(pattern, text)
; output identik dengan algoritma BMG.sumber
Python 2, 937 byte
Ini tidak pendek, dengan cara apa pun, tetapi (a) berfungsi, (b) memenuhi semua persyaratan, dan (c) bermain golf sebanyak yang saya bisa lakukan.
Ini adalah implementasi dari algoritma Boyer-Moore-Galil. Cukup mudah - panggilan dengan
S(pattern,text)
; dua fungsi lainnya digunakan dalam preprocessing. Memang, semuanya kecuali 5 baris terakhir adalah preprocessing.Contoh dijalankan, yang membutuhkan waktu sekitar satu detik:
sumber
O(m)
preprocessing danO(n)
pencocokan [=>O(n+m)
], yang dilakukan (atau lebih baik).O(n+m)
waktu tetapi membutuhkan waktu untuk salah satu simbol dalam teks, misalnya.KMP, Python 2 (213 byte)
Versi tidak disatukan. Loop pertama adalah untuk membangun automata KMP. Loop kedua berjalan di automata. Mereka berbagi hampir pola yang sama tetapi abstrak mereka akan memerlukan lebih banyak byte sehingga untuk kode golf saya lebih suka menduplikasi logika ini. Implementasi serupa sebenarnya banyak digunakan dalam kontes pemrograman.
sumber
KMP Realtime, Python 2 (167 byte)
Dalam KMP normal, kami mensimulasikan perilaku otomat dengan menggunakan fungsi gagal. Dalam KMP realtime ini, otomat penuh dikonstruksi sehingga dalam frasa yang cocok dapat memproses setiap karakter secara realtime (waktu konstan).
Kompleksitas waktu dan ruang preprocessing adalah O (nm), di mana m adalah ukuran alfabet dan n adalah panjang dari string pola. Namun, dalam pengujian saya, ukuran sebenarnya dari tabel transisi selalu kurang dari 2n jadi mungkin kita dapat membuktikan bahwa kompleksitas waktu dan ruang adalah O (n).
Versi tidak disatukan
sumber
Q, 146 Bytes
Uji
menghasilkan 15 dan 34
Catatan
Tidak terbatas pada alfabet (mendukung karakter ascii, dan peka huruf besar-kecil).
Tidak menggunakan operasi spesifik apa pun yang didefinisikan oleh Q over string -> bekerja pada string sebagai urutan (ops match, panjang, dll.)
Meminimalkan tabel transisi bergabung dengan semua karakter yang tidak dalam pola sebagai satu kelas karakter yang unik.
Saya bisa memeras kode sedikit. Ini merupakan upaya pertama untuk memvalidasi strategi solusi
Kunjungi setiap karakter teks tepat sekali, dan untuk setiap karakter input ada lompatan unik. Jadi saya menganggap bahwa pencarian cocok dengan 'waktu nyata'
Konstruksi tabel al state i dan char c mencari substring terpanjang yang berakhir pada i dan setelah menambahkan c adalah awalan dari S. Konstruksi tidak dioptimalkan, jadi saya tidak tahu apakah valid
Format input tidak cocok dengan bahasa. Melewati dua argumen string akan menghemat 16 Bytes
Penjelasan
global W mewakili pola dan S berhubungan dengan teks untuk pencarian
x:1_"\n "\:x
kode aneh untuk mengatasi persyaratan input (Q membutuhkan string multiline yang memiliki baris non-pertama indentasi, sehingga harus membuang ruang tambahan di depan setiap baris non-pertama)n::#W
menghitung panjang W dan menyimpan sebagai global nu::?W
menghitung karakter unik di W, dan simpan sebagai global uu?S
menghasilkan kelas characted untuk setiap karakter SBuat tabel transisi T dengan satu baris per karakter unik di W (ditambah satu ekstra), dan kolom untuk setiap indeks di W (ditambah satu ekstra). Baris tambahan sesuai dengan keadaan awal, dan kolom tambahan mengumpulkan karakter apa pun di S tetapi tidak dalam W. Strategi ini meminimalkan ukuran tabel
p:{$[n<#x;0;x~(#x)#W;#x;0]}
adalah fungsi yang mencari awalan terpanjangf:{{|/p'x}'((1_)\x#W),\:/:u}
adalah fungsi yang menghitung baris x dari TCari teks menggunakan tabel transisi.
T\[0;u?S]
iterates lebih dari 0 (keadaan awal) dan masing-masing kelas karakter S, menggunakan sebagai nilai baru nilai pada tabel transisi T [state] [charClass]. Status akhir memiliki nilai n, jadi kami mencari nilai itu dalam urutan status dan mengembalikannya disesuaikan (untuk menunjukkan posisi awal alih-alih posisi akhir dari setiap pertandingan)sumber
Boyer-Moore, Perl (50)
Perl mencoba menggunakan Boyer-Moore secara alami:
sumber