Rabin-Karp算法在C中进行模式搜索的程序

在这个问题中，我们给两个字符串一个文本和一个模式。我们的任务是为Rabin-Karp算法创建一个程序以进行模式搜索，它将找到文本字符串中所有出现的模式。

在这里，我们必须找到文本中所有出现的模式。

让我们举个例子来了解这个问题，

输入值

text = “xyztrwqxyzfg” pattern = “xyz”

输出结果

Found at index 0
Found at index 7

在这里，我们将讨论使用Rabin-Karp算法解决问题的方法。在此算法中，我们在字符串中采用模式大小的窗口，并将其一一滑动，然后将其与模式的哈希值进行匹配。如果哈希值匹配，那么我们将检查模式的各个字符是否与字符串匹配。

对于Rabin-Karp，文本和图案的哈希值很重要，对于图案的创建，我们将为每个字符添加字符的数值

通过将字符串和哈希的字符除以质数来考虑，以使该值变小，以考虑该字符。

Rabin-Karp模式搜索算法程序

//用于模式搜索的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