Fungsi Awalan KMP
Menemukan pola dalam O(n + m)
Fungsi Awalan KMP adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah Pencocokan Pola
Anda ingin menemukan posisi kemunculan pola kecil di dalam teks besar. Pemeriksaan naif lambat, jadi dalam kompetisi pemrograman diperlukan penelusuran yang lebih cerdas. 🔍
Mengapa Pencarian Naif Bermasalah
Membandingkan pola pada setiap posisi dapat memerlukan waktu O(n*m). Pada masukan besar, hal ini dapat diam-diam melampaui batas waktu Anda.
Berkenalan dengan Fungsi Awalan
Fungsi awalan mengukur, pada setiap posisi, prefiks sejati terpanjang yang juga merupakan sufiks. Fungsi ini adalah inti KMP.
Prefiks dan Sufiks Sejati
Prefiks atau sufiks sejati tidak mencakup seluruh string itu sendiri. Untuk ababa, pasangan yang cocok terpanjang memiliki panjang 3: aba.
Isi pi[i]
Kita menyimpan nilai-nilai tersebut dalam larik bernama pi. Di sini, pi[i] adalah panjang prefiks-sufiks terpanjang untuk potongan yang berakhir pada indeks i.
Membangun pi dalam Satu Lintasan
Anda membangun pi dari kiri ke kanan dengan menggunakan kembali nilai-nilai sebelumnya, bukan memeriksa ulang dari awal. Penggunaan kembali inilah inti triknya.
def prefix_function(s):
pi = [0] * len(s)
return piPerulangan Mundur
Ketika karakter tidak cocok, Anda mundur ke pi[k-1], bukan mengatur ulang ke nol. Dengan demikian, pekerjaan yang sama tidak perlu diulang.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Memperpanjang Kecocokan
Jika karakter saat ini cocok, tambah panjangnya satu dan catat hasilnya. Ketidakcocokan saat panjangnya nol cukup dibiarkan bernilai nol.
if s[i] == s[k]:
k += 1
pi[i] = kMencari dengan Trik Ini
Untuk mencari pola dalam teks, gabungkan keduanya sebagai pattern + sep + text. Nilai pi apa pun yang sama dengan panjang pola menandai kecocokan penuh.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Mengapa Pemisah Penting
Pemisah adalah simbol yang tidak terdapat dalam kedua string. Pemisah mencegah kecocokan merambat melewati titik penggabungan dan menghasilkan kecocokan palsu.
Keuntungan Waktu Linear
Pembangunan dan pencarian sama-sama berjalan dalam O(n + m). Setiap karakter diproses satu kali, sehingga KMP dapat menangani masukan kompetisi yang sangat besar.
Uji Cepat
Uji pemahaman Anda tentang hal yang dicatat oleh fungsi awalan.
Rangkuman: KMP secara Singkat
Anda telah mempelajari fungsi awalan: bangun pi sekali, mundur saat terjadi ketidakcocokan, lalu lakukan pencarian dalam waktu linear. Itulah KMP secara singkat. 🎯
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Fungsi Awalan KMP” gratis?
Ya — teks lengkap “Fungsi Awalan KMP” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Fungsi Awalan KMP”?
Menemukan pola dalam O(n + m) Kamu berlatih Coding Interview Prep 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep 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 1 dari 4.
Berapa lama pelajaran “Fungsi Awalan KMP” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.