ฟังก์ชันคำนำหน้า KMP
ค้นหารูปแบบใน O(n + m)
ฟังก์ชันคำนำหน้า KMP เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาการจับคู่รูปแบบ
คุณต้องการค้นหาว่ารูปแบบขนาดเล็กปรากฏอยู่ที่ใดในข้อความขนาดใหญ่ การตรวจสอบแบบตรงไปตรงมาช้า ดังนั้นโจทย์การแข่งขันจึงให้รางวัลกับการสแกนที่ฉลาดกว่า 🔍
เหตุใดการค้นหาแบบตรงไปตรงมาจึงช้า
การเปรียบเทียบรูปแบบที่ทุกตำแหน่งอาจใช้เวลา O(n*m) สำหรับข้อมูลขนาดใหญ่ วิธีนี้อาจทำให้เกินขีดจำกัดเวลาของคุณโดยไม่ทันสังเกต
พบกับฟังก์ชันคำนำหน้า
ฟังก์ชันคำนำหน้าวัดว่า ณ แต่ละตำแหน่ง คำนำหน้าที่ไม่ใช่ทั้งสตริงซึ่งยาวที่สุดและเป็นส่วนต่อท้ายด้วยมีความยาวเท่าใด ฟังก์ชันนี้เป็นหัวใจของ KMP
คำนำหน้าและส่วนต่อท้ายที่ไม่ใช่ทั้งสตริง
คำนำหน้าหรือส่วนต่อท้ายที่ไม่ใช่ทั้งสตริงจะไม่รวมสตริงทั้งหมดในตัวมันเอง สำหรับ ababa คู่ที่ตรงกันและยาวที่สุดมีความยาว 3 คือ aba
pi[i] เก็บอะไรไว้
เราเก็บค่าเหล่านี้ไว้ในอาร์เรย์ชื่อ pi โดย pi[i] คือความยาวของคำนำหน้าและส่วนต่อท้ายที่ตรงกันและยาวที่สุด สำหรับส่วนย่อยที่สิ้นสุดที่ดัชนี i
สร้าง pi ในรอบเดียว
คุณสร้าง pi จากซ้ายไปขวา โดยนำค่าที่คำนวณไว้ก่อนหน้ากลับมาใช้แทนการตรวจสอบใหม่ตั้งแต่ต้น การใช้ซ้ำนี้คือเคล็ดลับทั้งหมด
def prefix_function(s):
pi = [0] * len(s)
return piลูปการถอยกลับ
เมื่ออักขระไม่ตรงกัน ให้ถอยกลับไปที่ pi[k-1] แทนการตั้งค่าเป็นศูนย์ วิธีนี้ช่วยหลีกเลี่ยงการทำงานซ้ำ
while k > 0 and s[i] != s[k]:
k = pi[k - 1]ขยายส่วนที่ตรงกัน
หากอักขระปัจจุบันตรงกัน ให้เพิ่มความยาวขึ้นหนึ่งแล้วบันทึกค่าไว้ หากไม่ตรงกันขณะที่ค่าเป็นศูนย์ ก็ให้คงค่าเป็นศูนย์
if s[i] == s[k]:
k += 1
pi[i] = kค้นหาด้วยเคล็ดลับนี้
หากต้องการค้นหารูปแบบในข้อความ ให้เชื่อมทั้งสองเข้าด้วยกันเป็น pattern + sep + text ค่า pi ใดก็ตามที่เท่ากับความยาวของรูปแบบจะระบุว่าพบการจับคู่ครบถ้วน
combined = pattern + chr(0) + text
pi = prefix_function(combined)เหตุใดตัวคั่นจึงสำคัญ
ตัวคั่นคือสัญลักษณ์ที่ไม่อยู่ในสตริงทั้งสอง ตัวคั่นจะป้องกันไม่ให้การจับคู่ข้ามรอยต่อจนเกิดผลการจับคู่ผิดพลาด
ประโยชน์ของเวลาเชิงเส้น
ทั้งการสร้างและการค้นหาทำงานในเวลา O(n + m) อักขระทุกตัวถูกประมวลผลหนึ่งครั้ง ดังนั้น KMP จึงรองรับข้อมูลขนาดใหญ่มากในการแข่งขันได้
ตรวจสอบความเข้าใจ
ทดสอบความเข้าใจของคุณเกี่ยวกับสิ่งที่ฟังก์ชันคำนำหน้าบันทึกไว้
ทบทวน: KMP โดยสรุป
คุณได้เรียนรู้ฟังก์ชันคำนำหน้า: สร้าง pi หนึ่งครั้ง ถอยกลับเมื่ออักขระไม่ตรงกัน และค้นหาในเวลาเชิงเส้น นี่คือ KMP โดยสรุป 🎯
คำถามที่พบบ่อย
บทเรียน “ฟังก์ชันคำนำหน้า KMP” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ฟังก์ชันคำนำหน้า KMP” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ฟังก์ชันคำนำหน้า KMP”
ค้นหารูปแบบใน O(n + m) คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “ฟังก์ชันคำนำหน้า KMP” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ฟังก์ชันคำนำหน้า KMP
- แฮชสตริงพหุนาม
- ฟังก์ชัน Z สำหรับค้นหารูปแบบ
- ทรีไตรสำหรับค้นหาคำนำหน้า