โปรแกรม C สำหรับอัลกอริทึม Rabin-Karp ในการค้นหา Pattern

ในปัญหานี้ เราได้รับสตริง 2 ตัวคือ text และ pattern งานของเราคือสร้างโปรแกรมสำหรับอัลกอริทึม Rabin-Karp ในการค้นหา pattern เพื่อหาทุกครั้งที่ pattern ปรากฏใน text string

ที่นี่ เราต้องหาทุกครั้งที่ pattern ปรากฏใน text

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

text = "xyztrwqxyzfg" pattern = "xyz"

เอาต์พุต

Found at index 0 Found at index 7

ที่นี่ เราจะอภิปรายวิธีแก้ปัญหาโดยใช้ Rabin-Karp algorithm ในอัลกอริทึมนี้ เราจะใช้หน้าต่างขนาดเท่ากับ pattern ในสตริงและเลื่อนทีละตัว แล้วเปรียบเทียบกับค่าแฮชของ pattern หากค่าแฮชตรงกัน เราจะตรวจสอบต่อว่าตัวอักษรแต่ละตัวของ pattern ตรงกับสตริงหรือไม่

สำหรับ Rabin-Karp ค่าแฮชของ text และ pattern สำคัญมาก สำหรับการสร้าง pattern เราจะบวกค่าตัวเลขของตัวอักษรสำหรับทุกตัวอักษรของสตริง และแฮชจะถูกพิจารณาโดยการหารด้วยจำนวนเฉพาะเพื่อให้ค่านั้นเล็กลง

โปรแกรมสำหรับอัลกอริทึม Rabin-Karp ในการค้นหา Pattern

// Program for Rabin-Karp Algorithm for Pattern Searching

ตัวอย่าง

#include <stdio.h>
#include <string.h>
#define c 256
void search(char pattern[], char text[]){
    int M = strlen(pattern);
    int N = strlen(text);
    int i, j;
    int hashP = 0;
    int hashT = 0;
    int h = 1;
    for (i = 0; i < M - 1; i++)
        h = (h * c) % 103;
    for (i = 0; i < M; i++) {
        hashP = (c * hashP + pattern[i]) % 103;
        hashT = (c * hashT + text[i]) % 103;
    }
    for (i = 0; i <= N - M; i++) {
        if (hashP == hashT) {
            for (j = 0; j < M; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == M)
                printf("Pattern found at index %d \n", i);
        }
        if (i < N - M) {
            hashT = (c * (hashT - text[i] * h) + text[i + M]) % 103;
            if (hashT < 0)
                hashT = (hashT + 103);
        }
    }
}
int main(){
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    search(pattern, text);
    return 0;
}

ผลลัพธ์

The pattern is found in the text at the following index −

Pattern found at index 0
Pattern found at index 7