ขั้นตอนวิธีราบิน–คาร์ป

Rabin-Karp คือ อัลกอริทึมการจับคู่สตริงเป็นอัลกอริทึมที่สร้างขึ้นโดย Richard M. Karp และ Michael O. Rabin ที่ใช้เพื่อค้นหาชุดรูปแบบใด ๆ ในข้อความ สำหรับข้อความที่มีความยาว n และรูปแบบ p อัลกอริธึม Rabin Karp จะมีการหาค่าแฮชของรูปแบบสตริงย่อยปัจจุบันของข้อความ เนื่องจากเราจำเป็นต้องคำนวณค่าแฮชสำหรับสตริงย่อยทุกขนาด m ของข้อความเราต้องมีฟังก์ชันแฮช ฟังก์ชันแฮชที่แนะนำโดย Rabin และ Karp จะคำนวณค่าจำนวนเต็ม ค่าจำนวนเต็มสำหรับสตริงคือค่าตัวเลขของสตริง ตัวอย่างเช่นถ้าอักขระที่เป็นไปได้ทั้งหมดคือ 1 ถึง 10 ค่าตัวเลข "122" จะเป็น 122 จำนวนอักขระที่เป็นไปได้สูงกว่า 10 (256 โดยทั่วไป) และความยาวของรูปแบบอาจมีขนาดใหญ่ ดังนั้นค่าตัวเลขจึงไม่สามารถเก็บเป็นจำนวนเต็มได้ ดังนั้นค่าตัวเลขจะถูกคำนวณโดยใช้เลขคณิตแบบแยกส่วนเพื่อให้แน่ใจว่าค่าแฮชสามารถเก็บไว้ในตัวแปรจำนวนเต็ม

ตัวอย่าง

Text : A B C A B A Pattern : A B A h(“ABA”) = 78

Text : A B C A B A h(“ABC”) = 348 ≠ 78

Text : A B C A B A h(“BCA”) = 519 ≠ 78

Text : A B C A B A h(“CAB”) = 19 ≠ 78

Text : A B C A B A h(“CAB”) = 78 ≠ 78

ดังนั้น Pattern จะอยู่ใน index 3 ของ Text

^{หมายเหตุ ค่าของแฮชเป็นเพียงตัวเลขสมมุติ}

การนำ Rabin-Karpไปใช้งานในภาษาPython

ตัวอย่างภาษาไพทอน

def rabin_karp(text,pattern): p_len = len(pattern) p_hash = hash(pattern) for i in range(0, len(text) - (p_len - 1)): text_hash = hash(text[i:i + p_len]) if text_hash == p_hash and text[i:i + p_len] == pattern: return True return False 

เวลาเฉลี่ยที่ดีที่สุดของอัลกอริทึม Rabin-Karp คือ O (n + m) แต่เวลาที่แย่ที่สุดคือ O (nm) กรณีที่เลวร้ายที่สุดของอัลกอริทึม Rabin-Karp เกิดขึ้นเมื่ออักขระทั้งหมดของรูปแบบและข้อความเหมือนกับค่าแฮชของสตริงย่อยทั้งหมดของ txt [] ตรงกับค่าแฮชของ pat [] ตัวอย่างเช่น pat [] = "AAA" และ txt [] = "AAAAAAA"

อ้างอิง

Rabin-Karp Algorithm on geeksforgeeks