Fungsi Z untuk Pencarian Pola
Mencocokkan awalan di seluruh string
Fungsi Z untuk Pencarian Pola adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Alat Pencocokan Lain
Fungsi Z adalah alternatif sederhana untuk KMP dalam pencarian pola. Banyak orang merasa cara kerjanya lebih mudah dipahami. ✨
Makna z[i]
Untuk setiap indeks, z[i] adalah panjang subuntai terpanjang yang dimulai pada i dan juga cocok dengan prefiks seluruh untai.
Contoh Kecil
Untuk aabaab, z bernilai 0,1,0,3,1,0. Pada indeks 3, rangkaian aab cocok dengan prefiks sehingga panjangnya 3.
Kotak Z
Kita melacak jendela [l, r], yaitu kecocokan paling kanan yang telah ditemukan. Jendela ini memungkinkan kita menggunakan kembali perbandingan sebelumnya.
l, r = 0, 0Di Dalam Kotak
Saat i berada di dalam kotak, Anda menyalin nilai z yang diketahui sebagai titik awal, dengan batas tepi kotak.
if i < r:
z[i] = min(r - i, z[i - l])Memperpanjang Melewati Kotak
Setelah titik awal tersebut, Anda terus membandingkan karakter satu per satu selama semuanya cocok dengan prefiks.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Menggeser Kotak ke Depan
Jika kecocokan Anda mencapai lebih jauh ke kanan, perbarui l dan r agar indeks berikutnya dapat menggunakannya kembali.
if i + z[i] > r:
l, r = i, i + z[i]Jaminan Waktu Linear
Kotak hanya bergerak ke kanan, sehingga total pekerjaannya adalah O(n). Setiap karakter berkontribusi dalam jumlah yang terbatas.
Mencari dengan Z
Gabungkan pattern + sep + text lalu jalankan Z. Setiap nilai z yang sama dengan panjang pola menunjukkan adanya kecocokan.
combined = pattern + chr(0) + text
z = z_function(combined)Membaca Posisi Kecocokan
Pindai larik Z; di mana pun z[i] == len(pattern), kecocokan dimulai pada posisi yang sesuai di dalam teks.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z vs KMP
Z dan KMP sama-sama berjalan dalam waktu linear. Z sering kali lebih mudah ditulis, sehingga menjadi cadangan yang bagus dalam perangkat Anda.
Pemeriksaan Singkat
Pastikan makna larik Z sudah benar-benar dipahami.
Rangkuman: Fungsi Z Unggul
Anda telah membangun larik Z dengan kotak yang bergeser, melakukan pencarian dalam waktu linear, dan kini memiliki alternatif KMP yang sederhana. 🎯
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Fungsi Z untuk Pencarian Pola” gratis?
Ya — teks lengkap “Fungsi Z untuk Pencarian Pola” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Fungsi Z untuk Pencarian Pola”?
Mencocokkan awalan di seluruh string Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Fungsi Z untuk Pencarian Pola” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Fungsi Awalan KMP
- Hashing String Polinomial
- Fungsi Z untuk Pencarian Pola
- Trie untuk Pencarian Awalan