แฮชสตริงพหุนาม
เปรียบเทียบสตริงย่อยในเวลาคงที่
แฮชสตริงพหุนาม เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เปรียบเทียบสตริงย่อยอย่างรวดเร็ว
บ่อยครั้งคุณต้องตรวจสอบว่าสตริงย่อยสองส่วนเท่ากันหรือไม่ การตรวจทีละอักขระช้า เราจึงแปลงสตริงแต่ละส่วนให้เป็นตัวเลข 🔢
แนวคิดเรื่องแฮช
แฮชจะแปลงสตริงให้เป็นจำนวนเต็มหนึ่งค่า หากสตริงสองสตริงแตกต่างกัน ค่าแฮชของทั้งสองก็มักจะแตกต่างกันด้วย
มองสตริงเป็นพหุนาม
เราอ่านอักขระแต่ละตัวเป็นเลขโดดในฐาน p มุมมองแบบพหุนามนี้เปลี่ยนสตริงให้เป็นผลรวมถ่วงน้ำหนักขนาดใหญ่หนึ่งค่า
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * pเลือกฐานและโมดูลัส
เลือกฐานจำนวนเฉพาะ เช่น 31 และโมดูลัสจำนวนเฉพาะขนาดใหญ่ โมดูลัสช่วยให้ตัวเลขมีขนาดเล็กและป้องกันค่าล้น
BASE = 31
MOD = 10**9 + 9คำนวณแฮชหนึ่งค่า
เดินผ่านสตริงและรวมอักขระแต่ละตัวเข้าด้วยกันด้วยกฎของ Horner โดยคำนวณโมดูลัสในทุกขั้นตอน
h = 0
for c in s:
h = (h * BASE + ord(c)) % MODแฮชคำนำหน้า
เก็บแฮชคำนำหน้าไว้สำหรับทุกตำแหน่ง จากนั้นแฮชของสตริงย่อยใด ๆ จะคำนวณได้จากการลบอย่างรวดเร็ว
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MODเลขยกกำลังของฐาน
คุณต้องคำนวณเลขยกกำลังของฐานล่วงหน้าด้วย ค่าเหล่านี้จะช่วยปรับคำนำหน้าทั้งสองให้ตรงตำแหน่งกันเมื่อนำมาลบ
pw[i] = (pw[i - 1] * BASE) % MODแฮชสตริงย่อยในเวลา O(1)
แฮชของ s[l..r] คือการลบค่าแฮชคำนำหน้าสองค่า โดยปรับขนาดด้วยเลขยกกำลัง ใช้เวลาคงที่ต่อคิวรี
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MODระวังการชนกัน
สตริงที่แตกต่างกันสองชุดอาจมีค่าแฮชเดียวกันได้ ซึ่งเรียกว่า การชนกัน แม้จะเกิดขึ้นไม่บ่อย แต่บางครั้งข้อสอบอาจสร้างอินพุตเพื่อทำให้เกิดกรณีนี้
การแฮชสองชุดเพื่อความปลอดภัย
ใช้มอดูลัสที่เป็นอิสระต่อกัน สอง ค่า แล้วเปรียบเทียบค่าแฮชทั้งสอง การชนกันพร้อมกันทั้งสองค่าจึงแทบเป็นไปไม่ได้
จุดเด่นของการแฮช
การแฮชช่วยให้ทำ การเปรียบเทียบสตริงย่อย การค้นหาส่วนที่ซ้ำกัน และการค้นหารูปแบบได้อย่างมีประสิทธิภาพ จึงเป็นเครื่องมืออเนกประสงค์ที่ยืดหยุ่นมาก
ตรวจสอบอย่างรวดเร็ว
เลือกเครื่องมือที่เหมาะสมสำหรับการเปรียบเทียบสตริงย่อยจำนวนมากอย่างปลอดภัย
ทบทวน: การแฮชช่วยให้ชนะ
ขณะนี้คุณสามารถเปลี่ยนสตริงให้เป็น แฮชพหุนาม สอบถามสตริงย่อยใด ๆ ได้ใน O(1) และป้องกันการชนกันได้แล้ว 🚀
คำถามที่พบบ่อย
บทเรียน “แฮชสตริงพหุนาม” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “แฮชสตริงพหุนาม” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “แฮชสตริงพหุนาม”
เปรียบเทียบสตริงย่อยในเวลาคงที่ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “แฮชสตริงพหุนาม” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ