อัลกอริทึม Rabin-Karp สำหรับการค้นหาแพทเทิร์น

บทนำ

Rabin-Karp เป็นอัลกอริทึมค้นหาแพทเทิร์นที่มีประสิทธิภาพ ใช้วิธีเลื่อนหน้าต่าง (Sliding Window) แต่แทนที่จะตรวจสอบตัวอักษรทุกตัวทุกครั้ง จะคำนวณค่า Hash ก่อน เมื่อค่า Hash ตรงกันจึงตรวจสอบตัวอักษรจริง ทำให้เร็วขึ้นในกรณีทั่วไป

ความซับซ้อนของเวลา (Time Complexity)

O(m + n) ในกรณีทั่วไป แต่กรณีแย่ที่สุดคือ O(mn)

อินพุตและเอาต์พุต

Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern "ABC"
Output: Pattern found at position: 4
        Pattern found at position: 10
        Pattern found at position: 18

อัลกอริทึม

rabinKarpSearch(text, pattern, prime)

Input: ข้อความหลัก, แพทเทิร์น, จำนวนเฉพาะสำหรับคำนวณ Hash
Output: ตำแหน่งที่พบแพทเทิร์น

Begin
    patLen := ความยาว pattern
    strLen := ความยาว string
    patHash := 0, strHash := 0, h := 1
    maxChar := จำนวนตัวอักษรในชุดตัวอักษร
    
    for i := 0 ถึง patLen-1 do
        h := (h * maxChar) mod prime
    done
    
    for i := 0 ถึง patLen-1 do
        patHash := (maxChar * patHash + pattern[i]) mod prime
        strHash := (maxChar * strHash + text[i]) mod prime
    done
    
    for i := 0 ถึง (strLen - patLen) do
        if patHash = strHash then
            for charIndex := 0 ถึง patLen-1 do
                if text[i+charIndex] ≠ pattern[charIndex] then break
            done
            if charIndex = patLen then พิมพ์ตำแหน่ง i
        if i < (strLen - patLen) then
            strHash := (maxChar*(strHash - text[i]*h) + text[i+patLen]) mod prime
            if strHash < 0 then strHash := strHash + prime
    done
End

ตัวอย่างโค้ด (C++)

#include<iostream>
#define MAXCHAR 256
using namespace std;

void rabinKarpSearch(string mainString, string pattern, int prime, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int charIndex, pattHash = 0, strHash = 0, h = 1;
    
    for(int i = 0; i

ผลลัพธ์
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18