Fungsi Awalan KMP
Cari corak dalam O(n + m).
Fungsi Awalan KMP ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Masalah Pemadanan Corak
Anda ingin mencari tempat corak kecil muncul dalam teks yang besar. Semakan naif adalah lambat, jadi pertandingan pengaturcaraan memberi ganjaran kepada imbasan yang lebih bijak. 🔍
Mengapa Carian Naif Membebankan
Membandingkan corak pada setiap kedudukan boleh mengambil masa O(n*m). Pada input besar, kaedah ini boleh melampaui had masa anda tanpa disedari.
Kenali Fungsi Awalan
Fungsi awalan mengukur, pada setiap kedudukan, awalan sejati terpanjang yang juga merupakan akhiran. Fungsi ini ialah teras KMP.
Awalan dan Akhiran Sejati
Awalan atau akhiran sejati tidak merangkumi keseluruhan rentetan itu sendiri. Bagi ababa, pasangan sepadan terpanjang mempunyai panjang 3: aba.
Perkara yang Disimpan oleh pi[i]
Kami menyimpan nilai tersebut dalam tatasusunan bernama pi. Di sini pi[i] ialah panjang awalan-akhiran terpanjang bagi potongan yang berakhir pada indeks i.
Membina pi dalam Satu Laluan
Anda membina pi dari kiri ke kanan dengan menggunakan semula nilai terdahulu dan bukannya menyemak semula dari awal. Penggunaan semula itulah helah utamanya.
def prefix_function(s):
pi = [0] * len(s)
return piGelung Sandaran
Apabila aksara tidak sepadan, beralih kepada pi[k-1] dan bukannya menetapkan semula kepada sifar. Ini mengelakkan kerja berulang.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Memanjangkan Padanan
Jika aksara semasa sepadan, tambah panjang sebanyak satu dan rekodkan nilainya. Ketidakpadanan pada sifar kekal sifar.
if s[i] == s[k]:
k += 1
pi[i] = kMencari dengan Helah Ini
Untuk mencari corak dalam teks, cantumkan kedua-duanya sebagai pattern + sep + text. Mana-mana nilai pi yang sama dengan panjang corak menandakan padanan penuh.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Mengapa Pemisah Penting
Pemisah ialah simbol yang tiada dalam mana-mana rentetan. Simbol ini menghalang padanan daripada merentasi cantuman dan menghasilkan padanan palsu.
Manfaat Masa Linear
Pembinaan dan carian kedua-duanya berjalan dalam O(n + m). Setiap aksara diproses sekali, jadi KMP boleh mengendalikan input pertandingan yang sangat besar.
Semakan Pantas
Uji kefahaman anda tentang perkara yang direkodkan oleh fungsi awalan.
Rumusan: KMP secara Ringkas
Anda telah mempelajari fungsi awalan: bina pi sekali, gunakan nilai sandaran apabila berlaku ketidakpadanan, dan lakukan carian dalam masa linear. Itulah KMP secara ringkas. 🎯
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Fungsi Awalan KMP” percuma?
Ya — teks penuh “Fungsi Awalan KMP” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Fungsi Awalan KMP”?
Cari corak dalam O(n + m). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.
Berapa lamakah pelajaran “Fungsi Awalan KMP” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Fungsi Awalan KMP
- Pencincangan Rentetan Polinomial
- Fungsi-Z untuk Carian Corak
- Trie untuk Carian Awalan