ฟังก์ชัน Z สำหรับค้นหารูปแบบ
จับคู่คำนำหน้าตลอดทั้งสตริง
ฟังก์ชัน Z สำหรับค้นหารูปแบบ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เครื่องมือจับคู่อีกแบบ
ฟังก์ชัน Z เป็นทางเลือกที่กระชับแทน KMP สำหรับการค้นหารูปแบบ หลายคนมองว่าทำความเข้าใจได้ง่ายกว่า ✨
ความหมายของ z[i]
สำหรับแต่ละดัชนี z[i] คือความยาวของสตริงย่อยที่ยาวที่สุดซึ่งเริ่มต้นที่ i และตรงกับคำนำหน้าของสตริงทั้งหมดด้วย
ตัวอย่างสั้น ๆ
สำหรับ aabaab ค่า z คือ 0,1,0,3,1,0 ที่ดัชนี 3 ช่วง aab ตรงกับคำนำหน้า จึงมีความยาว 3
กล่อง Z
เราติดตามช่วง [l, r] ซึ่งเป็นช่วงการจับคู่ที่อยู่ขวาสุดเท่าที่พบจนถึงตอนนี้ ช่วงนี้ช่วยให้เรานำผลการเปรียบเทียบก่อนหน้ากลับมาใช้ได้
l, r = 0, 0ภายในกล่อง
เมื่อ i อยู่ภายในกล่อง คุณจะ คัดลอกค่า z ที่ทราบมาใช้เป็นจุดเริ่มต้น โดยจำกัดค่าไม่ให้เกินขอบของกล่อง
if i < r:
z[i] = min(r - i, z[i - l])ขยายเลยกล่อง
หลังจากจุดเริ่มต้น คุณจะ เปรียบเทียบอักขระทีละตัวต่อไป ตราบใดที่อักขระเหล่านั้นยังตรงกับคำนำหน้า
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1เลื่อนกล่องไปข้างหน้า
หากการจับคู่ไปได้ไกลทางขวามากกว่าเดิม ให้ ปรับปรุงค่า l และ r เพื่อให้ดัชนีถัดไปนำช่วงนี้กลับมาใช้ได้
if i + z[i] > r:
l, r = i, i + z[i]รับประกันเวลาเชิงเส้น
กล่องจะเลื่อนไปทางขวาเท่านั้น ดังนั้นงานทั้งหมดจึงใช้เวลา O(n) อักขระแต่ละตัวมีส่วนร่วมในปริมาณที่มีขอบเขตจำกัด
ค้นหาด้วย Z
นำ รูปแบบ + ตัวคั่น + ข้อความ มาต่อกันแล้วคำนวณ Z ค่า z ใด ๆ ที่เท่ากับความยาวของรูปแบบหมายถึงพบการจับคู่
combined = pattern + chr(0) + text
z = z_function(combined)อ่านตำแหน่งการจับคู่
ไล่ดูอาร์เรย์ Z ทุกตำแหน่งที่ z[i] == len(pattern) คือจุดเริ่มต้นของการจับคู่ ณ ตำแหน่งที่สอดคล้องกันในข้อความ
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z เทียบกับ KMP
Z และ KMP ต่างก็ทำงานใน เวลาเชิงเส้น โดยทั่วไป Z เขียนโค้ดได้ง่ายกว่า จึงเป็นทางเลือกสำรองที่ดีในชุดเครื่องมือของคุณ
ตรวจสอบอย่างรวดเร็ว
ตรวจสอบให้แน่ใจว่าคุณเข้าใจความหมายของอาร์เรย์ Z อย่างชัดเจนแล้ว
ทบทวน: ฟังก์ชัน Z ช่วยให้ชนะ
คุณสร้าง อาร์เรย์ Z ด้วยกล่องที่เลื่อนไปมา ค้นหาได้ในเวลาเชิงเส้น และมีทางเลือกที่กระชับแทน KMP แล้ว 🎯
คำถามที่พบบ่อย
บทเรียน “ฟังก์ชัน Z สำหรับค้นหารูปแบบ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ฟังก์ชัน Z สำหรับค้นหารูปแบบ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ฟังก์ชัน Z สำหรับค้นหารูปแบบ”
จับคู่คำนำหน้าตลอดทั้งสตริง คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ฟังก์ชัน Z สำหรับค้นหารูปแบบ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ฟังก์ชันคำนำหน้า KMP
- แฮชสตริงพหุนาม
- ฟังก์ชัน Z สำหรับค้นหารูปแบบ
- ทรีไตรสำหรับค้นหาคำนำหน้า