Rabin-Karp算法用于模式搜索的C程序
C中的模式匹配 -我们必须找出另一个字符串中是否存在一个字符串，例如，字符串“algorithm”出现在字符串“naivealgorithm”中。如果找到，则其位置（即位置为我们倾向于创建一个函数，该函数接收2个字符数组，如果匹配发生，则返回位置，否则返回-1。
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 Pattern found at index 9 Pattern found at index 12
Rabin-Karp是另一种模式搜索算法。Rabin和Karp提出的字符串匹配算法可以更有效地找到模式。与朴素算法一样，它也通过逐个移动窗口来检查模式，但是在不检查所有情况下所有字符的情况下，它会找到哈希值。当哈希值匹配时，只有它继续检查每个字符。这样，每个文本子序列只有一个比较，这使其成为一种更有效的模式搜索算法。
预处理时间-O(m)
Rabin-Karp算法的时间复杂度为O（m+n），但最坏的情况是O(mn)。
算法
rabinkarp_algo（文字，图案，素数）
输入 -主要文本和样式。查找哈希位置的另一个素数
输出 -找到模式的位置
Start
pat_len := pattern Length
str_len := string Length
patHash := 0 and strHash := 0, h := 1
maxChar := total number of characters in character set
for index i of all character in the pattern, do
h := (h*maxChar) mod prime
for all character index i of pattern, do
patHash := (maxChar*patHash + pattern[i]) mod prime
strHash := (maxChar*strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
if patHash = strHash, then
for charIndex := 0 to pat_len -1, do
if text[i+charIndex] ≠ pattern[charIndex], then
break
if charIndex = pat_len, then
print the location i as pattern found at i position.
if i < (str_len - pat_len), then
strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then
if strHash < 0, then
strHash := strHash + prime
End示例
#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;
int p = 0;
int t = 0;
int 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 nhoooisthebestprogrammingwebsite Enter the pattern to be searched p Enter a prime number 3 Pattern found at index 8 Pattern found at index 21