Trie untuk Pencarian Awalan
Menyimpan dan mencari awalan kata dengan cepat
Trie untuk Pencarian Awalan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 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.
Menyimpan Kata secara Cerdas
Pohon prefiks adalah pohon yang menyimpan kata dengan berbagi prefiks yang sama. Struktur ini membuat pertanyaan tentang prefiks menjadi sangat cepat. 🌳
Mengapa Tidak Cukup Menggunakan Himpunan
Himpunan dapat menjawab pencarian kata lengkap, tetapi pohon prefiks juga dapat menjawab pertanyaan tentang prefiks, misalnya apakah ada kata yang diawali dengan pre.
Simpul dan Sisi
Setiap simpul adalah sebuah posisi dalam suatu kata, sedangkan setiap sisi diberi label karakter pada jalur dari akar.
Anak sebagai Kamus
Di Python, simpul yang paling mudah dibuat adalah kamus yang memetakan karakter ke simpul anaknya. Sederhana dan fleksibel.
root = {}Menyisipkan Kata
Untuk menyisipkan kata, telusuri karakter satu per satu dan buat anak baru jika belum ada.
node = root
for c in word:
node = node.setdefault(c, {})Menandai Akhir Kata
Setelah menyisipkan kata, tetapkan penanda akhir agar Anda dapat membedakan kata lengkap dari sekadar prefiks.
node['#'] = TrueMencari Kata Lengkap
Untuk mencari, ikuti setiap karakter; jika ada langkah yang tidak tersedia, kata tersebut tidak ada. Setelah itu, periksa penanda akhir.
for c in word:
if c not in node:
return False
node = node[c]Memeriksa Prefiks
Pertanyaan tentang prefiks menggunakan penelusuran yang sama, tetapi pemeriksaan penanda akhir dilewati. Jika mencapai simpul terakhir, jawabannya adalah ya.
Kompleksitas Waktu
Penyisipan dan pencarian membutuhkan O(L), yaitu panjang kata, berapa pun jumlah kata yang disimpan. Panjanglah yang menentukan.
Menghitung Kata berdasarkan Prefiks
Simpan jumlah pada setiap simpul untuk segera menjawab berapa banyak kata tersimpan yang memiliki prefiks tertentu.
Kegunaan Pohon Prefiks
Pohon prefiks mendukung pelengkapan otomatis, pemeriksaan kamus, dan persoalan bit dengan XOR maksimum. Struktur ini merupakan andalan dalam persoalan untai di kontes.
Pemeriksaan Singkat
Pastikan Anda memahami biaya pencarian pada pohon prefiks.
Rangkuman: Pohon Prefiks Selesai
Sekarang Anda dapat membuat pohon prefiks, menyisipkan dan mencari dalam O(L), serta menjawab pertanyaan tentang prefiks dan jumlah dengan cepat. 🌟
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Trie untuk Pencarian Awalan” gratis?
Ya — teks lengkap “Trie untuk Pencarian Awalan” 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 “Trie untuk Pencarian Awalan”?
Menyimpan dan mencari awalan kata dengan cepat 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 4 dari 4.
Berapa lama pelajaran “Trie untuk Pencarian Awalan” 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