数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法学用 C 编写的 Rabin-Karp 算法模式搜索程序
在该问题中，我们给定两个字符串文本和模式。我们的任务是创建一个用于模式搜索的 Rabin-Karp 算法程序，它将找到文本字符串中模式的所有出现。
在此，我们必须找到文本中模式的所有出现。
我们举个例子来理解这个问题：
输入
text = “xyztrwqxyzfg” pattern = “xyz”
输出
Found at index 0 Found at index 7
在此，我们将使用 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
", 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 :
");
search(pattern, text);
return 0;
}输出
在以下索引处找到文本中的模式 -
Pattern found at index 0 Pattern found at index 7
更新日期：17-Jul-2020
310 次浏览
广告