โปรแกรม C สำหรับ Rabin-Karp Algorithm ในการค้นหาแพทเทิร์น

Pattern matching ใน C - หาว่าสตริงหนึ่งอยู่ในอีกสตริงหนึ่งหรือไม่ เช่น "algorithm" อยู่ใน "naive algorithm" หากเจอ แสดงตำแหน่ง (index)

Input: txt = "HERE IS A NICE CAP"  pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"  pattern = "XYZX"
Output: Pattern found at index 0, 9, 12

Rabin-Karp เป็นอัลกอริทึมค้นหาแพทเทิร์นอีกตัวหนึ่ง ใช้ hash value เพื่อค้นหาได้มีประสิทธิภาพมากกว่า Naive Algorithm ตรวจสอบตัวอักษรทีละตัวก็ต่อเมื่อ hash value ตรงกัน

Preprocessing time: O(m)

Time complexity: O(m+n) แต่อาจเป็น O(mn) ใน worst case

อัลกอริทึม

rabinkarp_algo(text, pattern, prime):
    pat_len = pattern length
    str_len = string length
    patHash = 0, strHash = 0, h = 1
    maxChar = จำนวนตัวอักษรในชุดตัวอักษร
    คำนวณ h = (h * maxChar) mod prime
    คำนวณ hash เริ่มต้นของ pattern และ text
    for i = 0 to (str_len - pat_len):
        if patHash == strHash:
            ตรวจสอบตัวอักษรทีละตัว
            ถ้าตรงทุกตัว พิมพ์ตำแหน่ง i
        อัปเดต strHash สำหรับ window ถัดไป
        if strHash < 0: strHash += prime

ตัวอย่างโค้ด

#include <stdio.h>
#include <string.h>

int main() {
    char txt[80], pat[80];
    int q;
    printf("Enter the container string \n");
    scanf("%s", txt);
    printf("Enter the pattern to be searched \n");
    scanf("%s", pat);
    int d = 256;
    printf("Enter a prime number \n");
    scanf("%d", &q);
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j, p = 0, t = 0, h = 1;
    for (i = 0; i < M - 1; i++) h = (h * d) % q;
    for (i = 0; i < M; i++) {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }
    for (i = 0; i <= N - M; i++) {
        if (p == t) {
            for (j = 0; j < M; j++)
                if (txt[i + j] != pat[j]) break;
            if (j == M) printf("Pattern found at index %d \n", i);
        }
        if (i < N - M) {
            t = (d * (t - txt[i] * h) + txt[i + M]) % q;
            if (t < 0) t = (t + q);
        }
    }
    return 0;
}

เอาต์พุต

Enter the container string
tutorialspointisthebestprogrammingwebsite
Enter the pattern to be searched
p
Enter a prime number
3
Pattern found at index 8
Pattern found at index 21