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