C言語でのパターン検索のためのラビン-カープアルゴリズムのプログラム

この問題では、テキストとパターンの2つの文字列が与えられます。私たちのタスクは、パターン検索用のRabin-Karpアルゴリズムのプログラムを作成することです。これにより、テキスト文字列内のすべてのパターンが検出されます。

ここでは、テキスト内のパターンのすべての出現箇所を見つける必要があります。

問題を理解するために例を見てみましょう

入力

text = “xyztrwqxyzfg” pattern = “xyz”

出力

Found at index 0
Found at index 7

ここでは、ラビン-カープアルゴリズムを使用した問題の解決について説明します。このアルゴリズムでは、文字列内のパターンのサイズのウィンドウを取得し、それを1つずつスライドさせて、パターンのハッシュ値と一致させます。また、ハッシュ値が一致する場合は、パターンの個々の文字が文字列と一致するかどうかを確認します。

Rabin-Karpの場合、テキストとパターンのハッシュ値が重要です。パターンの作成では、すべての文字の数値を追加します

文字列とハッシュの文字は、値を小さくするために素数で割ることによって考慮されます。

パターン検索のためのラビン-カープアルゴリズムのプログラム

//パターン検索用のラビン-カープアルゴリズムのプログラム

例

#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;
}

出力

このパターンは、テキストの次のインデックスにあります-

Pattern found at index 0
Pattern found at index 7