Hashing String Polinomial
Membandingkan substring dalam waktu konstan
Hashing String Polinomial adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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.
Membandingkan Subteks dengan Cepat
Anda sering perlu memeriksa apakah dua subteks sama. Pemeriksaan karakter demi karakter lambat, jadi kita mengubah setiap string menjadi sebuah angka. 🔢
Gagasan Pencacahan
Nilai pencacah memetakan sebuah string menjadi satu bilangan bulat. Jika dua string berbeda, nilai pencacahnya hampir selalu berbeda juga.
Perlakukan String sebagai Polinom
Kita membaca setiap karakter sebagai digit dalam basis p. Pandangan polinomial ini mengubah string menjadi satu jumlah berbobot yang besar.
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * pPilih Basis dan Modulus
Pilih basis prima seperti 31 dan modulus prima yang besar. Operasi modulo menjaga bilangan tetap kecil dan mencegah luapan.
BASE = 31
MOD = 10**9 + 9Menghitung Satu Nilai Pencacah
Telusuri string dan gabungkan setiap karakter menggunakan aturan Horner, dengan mengambil modulo pada setiap langkah.
h = 0
for c in s:
h = (h * BASE + ord(c)) % MODNilai Pencacah Prefiks
Simpan nilai pencacah prefiks untuk setiap posisi. Setelah itu, nilai pencacah subteks mana pun dapat diperoleh melalui pengurangan cepat.
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MODPangkat Basis
Anda juga perlu menghitung terlebih dahulu pangkat basis. Pangkat-pangkat ini menyelaraskan kedua prefiks saat Anda melakukan pengurangan.
pw[i] = (pw[i - 1] * BASE) % MODNilai Pencacah Subteks dalam O(1)
Nilai pencacah s[l..r] adalah hasil pengurangan dua nilai pencacah prefiks yang diskalakan dengan suatu pangkat. Waktu konstan untuk setiap kueri.
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MODWaspadai Benturan
Dua untai berbeda dapat memiliki nilai pencincangan yang sama; itulah benturan. Hal ini jarang terjadi, tetapi kontes terkadang sengaja membuat masukan yang memicunya.
Pencincangan Ganda untuk Keamanan
Gunakan dua modulus independen dan bandingkan kedua nilai pencincangan. Benturan pada keduanya sekaligus praktis mustahil.
Kegunaan Utama Pencincangan
Pencincangan memungkinkan perbandingan subuntai, pencarian pengulangan, dan pencarian pola. Ini adalah alat serbaguna.
Pemeriksaan Singkat
Pilih alat yang tepat untuk membandingkan banyak subuntai dengan aman.
Rangkuman: Pencincangan Unggul
Sekarang Anda dapat mengubah untai menjadi nilai pencincangan polinomial, menanyakan subuntai apa pun dalam O(1), dan melindungi diri dari benturan. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Hashing String Polinomial” gratis?
Ya — teks lengkap “Hashing String Polinomial” 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 “Hashing String Polinomial”?
Membandingkan substring dalam waktu konstan 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 2 dari 4.
Berapa lama pelajaran “Hashing String Polinomial” 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.
Semua pelajaran dalam kursus ini
- Fungsi Awalan KMP
- Hashing String Polinomial
- Fungsi Z untuk Pencarian Pola
- Trie untuk Pencarian Awalan