Rabin-Karp 算法
Rabin-Karp 算法是一种模式匹配算法，它使用哈希函数比较模式和文本。此处，术语哈希指的是将较大的输入值映射到较小的输出值（称为哈希值）的过程。此过程有助于避免不必要的比较，从而优化算法的复杂度。因此，Rabin-Karp 算法的时间复杂度为O(n + m)，其中 n 是文本的长度，m 是模式的长度。
Rabin-Karp 算法如何工作？
Rabin-Karp 算法通过逐个移动窗口来检查文本中的给定模式，但不会检查所有情况的所有字符，而是找到哈希值。然后，将其与文本中所有与模式长度相同的子字符串的哈希值进行比较。
如果哈希值匹配，则模式和子字符串可能相等，我们可以通过逐个字符比较来验证。如果哈希值不匹配，则可以跳过该子字符串，继续处理下一个子字符串。在下一节中，我们将了解如何计算哈希值。
使用 Rabin Karp 算法计算哈希值
计算哈希值的步骤如下 −
步骤 1：分配模数和基数
假设我们有文本 Txt = "DAACABCDBA" 和模式 Ptrn = "CAB"。我们首先根据文本字符的排序为其分配数值。最左边的字符的等级为 1，最右边的字符的等级为 10。此外，我们的哈希函数使用基数 b = 10（文本中的字符数）和模数 m = 11。需要注意的是，模数 m 必须是素数，因为它有助于避免溢出问题。
步骤 2：计算模式的哈希值
计算模式哈希值的公式如下：−
哈希值 (Ptrn) = Σ(r * bl-i-1) mod 11 其中，r：字符的排序 l：模式的长度 i：模式中字符的索引
因此，Patrn 的哈希值为 −
h(Ptrn) = ((4 * 102) + (5 * 101) + (6 * 100)) mod 11
= 456 mod 11
= 5
步骤 3：计算第一个文本窗口的哈希值
通过滑动文本中的所有字符，开始计算它们的哈希值。我们将从如下所示的第一个子字符串开始 −
h(DAA) = ((1 * 102) + (2 * 101) + (3 * 100)) mod 11
= 123 mod 11
= 6
现在，比较模式和子字符串的哈希值。如果匹配，则检查字符是否匹配。如果匹配，则表示我们找到了匹配项；否则，移至下一个字符。
在上面的例子中，哈希值不匹配。因此，我们移至下一个字符。
步骤 4：更新哈希值
现在，我们需要删除前一个字符并移至下一个字符。在此过程中，哈希值也应更新，直到找到匹配项。
示例
以下示例实际演示了 Rabin-Karp 算法的工作原理。
#include<stdio.h>
#include<string.h>
#define MAXCHAR 256
// 执行 Rabin-Karp 算法的函数
void rabinKSearch(char orgnlString[], char pattern[], int prime, int array[], int *index) {
int patLen = strlen(pattern);
int strLen = strlen(orgnlString);
int charIndex, pattHash = 0, strHash = 0, h = 1;
// 计算辅助变量的值
for(int i = 0; i<patLen-1; i++) {
h = (h*MAXCHAR) % prime;
}
// 计算初始哈希值和第一个窗口
for(int i = 0; i<patLen; i++) {
pattHash = (MAXCHAR*pattHash + pattern[i]) % prime;
strHash = (MAXCHAR*strHash + orgnlString[i]) % prime;
}
// 将图案逐一滑到文本上
for(int i = 0; i<=(strLen-patLen); i++) {
// 检查当前窗口的文本和图案的哈希值
if(pattHash == strHash) {
for(charIndex = 0; charIndex < patLen; charIndex++) {
if(orgnlString[i+charIndex] != pattern[charIndex])
break;
}
if(charIndex == patLen) {
(*index)++;
array[(*index)] = i;
}
}
// 计算下一个文本窗口的哈希值
if(i < (strLen-patLen)) {
strHash = (MAXCHAR*(strHash - orgnlString[i]*h) + orgnlString[i+patLen])%prime;
// 如果 strHash 为负数，则将其转换为正数
if(strHash < 0) {
strHash += prime;
}
}
}
}
int main() {
char orgnlString[] = "AAAABCAEAAABCBDDAAAABC";
char pattern[] = "AABC";
int locArray[strlen(orgnlString)];
int prime = 101;
int index = -1;
// 调用 Rabin-Karp 搜索函数
rabinKSearch(orgnlString, pattern, prime, locArray, &index);
for(int i = 0; i <= index; i++) {
printf("在以下位置找到图案： %d
", locArray[i]);
}
return 0;
}
#include<iostream>
#define MAXCHAR 256
using namespace std;
// 执行 Rabin-Karp 算法的函数
void rabinKSearch(string orgnlString, string pattern, int prime, int array[], int *index) {
int patLen = pattern.size();
int strLen = orgnlString.size();
int charIndex, pattHash = 0, strHash = 0, h = 1;
// 计算辅助变量的值
for(int i = 0; i<patLen-1; i++) {
h = (h*MAXCHAR) % prime;
}
// 计算初始哈希值和第一个窗口
for(int i = 0; i<patLen; i++) {
pattHash = (MAXCHAR*pattHash + pattern[i]) % prime;
strHash = (MAXCHAR*strHash + orgnlString[i]) % prime;
}
// 将图案逐一滑到文本上
for(int i = 0; i<=(strLen-patLen); i++) {
// 检查当前窗口的文本和图案的哈希值
if(pattHash == strHash) {
for(charIndex = 0; charIndex < patLen; charIndex++) {
if(orgnlString[i+charIndex] != pattern[charIndex])
break;
}
if(charIndex == patLen) {
(*index)++;
array[(*index)] = i;
}
}
// 计算下一个文本窗口的哈希值
if(i < (strLen-patLen)) {
strHash = (MAXCHAR*(strHash - orgnlString[i]*h) + orgnlString[i+patLen])%prime;
// 如果 strHash 为负数，则将其转换为正数
if(strHash < 0) {
strHash += prime;
}
}
}
}
int main() {
string orgnlString = "AAAABCAEAAABCBDDAAAABC";
// 要搜索的模式
string pattern = "AABC";
// 用于存储图案位置的数组
int locArray[orgnlString.size()];
int prime = 101;
int index = -1;
// 调用 Rabin-Karp 搜索函数
rabinKSearch(orgnlString, pattern, prime, locArray, &index);
// 打印结果
for(int i = 0; i <= index; i++) {
cout << "在以下位置找到图案： " << locArray[i]<<endl;
}
}
import java.util.ArrayList;
public class Main {
static final int MAXCHAR = 256;
// 执行Rabin-Karp算法的方法
static void rabinKSearch(String orgnlString, String pattern, int prime, ArrayList<Integer> locArray) {
int patLen = pattern.length();
int strLen = orgnlString.length();
int charIndex, pattHash = 0, strHash = 0, h = 1;
// 计算辅助变量的值
for (int i = 0; i < patLen - 1; i++) {
h = (h * MAXCHAR) % prime;
}
// 计算初始哈希值和第一个窗口
for (int i = 0; i < patLen; i++) {
pattHash = (MAXCHAR * pattHash + pattern.charAt(i)) % prime;
strHash = (MAXCHAR * strHash + orgnlString.charAt(i)) % prime;
}
// 将图案逐一滑到文本上
for (int i = 0; i <= (strLen - patLen); i++) {
// 检查当前窗口的文本和图案的哈希值
if (pattHash == strHash) {
for (charIndex = 0; charIndex < patLen; charIndex++) {
if (orgnlString.charAt(i + charIndex) != pattern.charAt(charIndex))
break;
}
if (charIndex == patLen) {
locArray.add(i);
}
}
// 计算下一个文本窗口的哈希值
if (i < (strLen - patLen)) {
strHash = (MAXCHAR * (strHash - orgnlString.charAt(i) * h) + orgnlString.charAt(i + patLen)) % prime;
// 如果 strHash 为负数，则将其转换为正数
if (strHash < 0) {
strHash += prime;
}
}
}
}
public static void main(String[] args) {
String orgnlString = "AAAABCAEAAABCBDDAAAABC";
// 要搜索的模式
String pattern = "AABC";
// 用于存储图案位置的数组
ArrayList<Integer> locArray = new ArrayList<>();
int prime = 101;
// 调用 Rabin-Karp 方法
rabinKSearch(orgnlString, pattern, prime, locArray);
// 打印结果
for (int i = 0; i < locArray.size(); i++) {
System.out.println("在以下位置找到图案： " + locArray.get(i));
}
}
}
MAXCHAR = 256
# 执行Rabin-Karp算法的方法
def rabinKSearch(orgnlString, pattern, prime):
patLen = len(pattern)
strLen = len(orgnlString)
pattHash = 0
strHash = 0
h = 1
locArray = []
# 计算辅助变量的值
for i in range(patLen-1):
h = (h*MAXCHAR) % prime
# 计算初始哈希值和第一个窗口
for i in range(patLen):
pattHash = (MAXCHAR*pattHash + ord(pattern[i])) % prime
strHash = (MAXCHAR*strHash + ord(orgnlString[i])) % prime
# 将图案逐一滑到文本上
for i in range(strLen-patLen+1):
if pattHash == strHash:
for charIndex in range(patLen):
if orgnlString[i+charIndex] != pattern[charIndex]:
break
else:
locArray.append(i)
# 计算下一个文本窗口的哈希值
if i < strLen-patLen:
strHash = (MAXCHAR*(strHash - ord(orgnlString[i])*h) + ord(orgnlString[i+patLen])) % prime
if strHash < 0:
strHash += prime
return locArray
def main():
orgnlString = "AAAABCAEAAABCBDDAAAABC"
pattern = "AABC"
prime = 101
locArray = rabinKSearch(orgnlString, pattern, prime)
for i in locArray:
print(f"在以下位置找到图案： {i}")
if __name__ == "__main__":
main()
Output
在以下位置找到图案： 2 在以下位置找到图案： 9 在以下位置找到图案： 18
