Rabin-Karp算法
Rabin-Karp是另一种模式搜索算法，可以更有效地找到模式。它还通过逐个移动窗口来检查模式，但是在不检查所有情况下所有字符的情况下，它会找到哈希值。当哈希值匹配时，只有它尝试检查每个字符。此过程使算法更有效。
时间复杂度为O（m+n），但在最坏的情况下为O(mn)。
输入输出
Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern “ABC” Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
算法
rabinKarpSearch(text, pattern, prime)
输入-主要文本和样式。查找哈希位置的另一个素数
输出-找到样式的位置
Begin
patLen := pattern Length
strLen := string Length
patHash := 0 and strHash := 0, h := 1
maxChar := total number of characters in character set
for index i of all character in pattern, do
h := (h*maxChar) mod prime
done
for all character index i of pattern, do
patHash := (maxChar*patHash + pattern[i]) mod prime
strHash := (maxChar*strHash + text[i]) mod prime
done
for i := 0 to (strLen - patLen), do
if patHash = strHash, then
for charIndex := 0 to patLen -1, do
if text[i+charIndex] ≠ pattern[charIndex], then
break the loop
done
if charIndex = patLen, then
print the location i as pattern found at i position.
if i < (strLen - patLen), then
strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then
if strHash < 0, then
strHash := strHash + prime
done
End示例
#include<iostream>
#define MAXCHAR 256
using namespace std;
void rabinKarpSearch(string mainString, string pattern, int prime, int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
int charIndex, pattHash = 0, strHash = 0, h = 1;
for(int i = 0; i<patLen-1; i++) {
h = (h*MAXCHAR) % prime; //calculating h = {d^(M-1)} mod prime
}
for(int i = 0; i<patLen; i++) {
pattHash = (MAXCHAR*pattHash + pattern[i]) % prime; //pattern hash value
strHash = (MAXCHAR*strHash + mainString[i]) % prime; //hash for first window
}
for(int i = 0; i<=(strLen-patLen); i++) {
if(pattHash == strHash) { //when hash values are same check for matching
for(charIndex = 0; charIndex < patLen; charIndex++) {
if(mainString[i+charIndex] != pattern[charIndex])
break;
}
if(charIndex == patLen) { //the pattern is found
(*index)++;
array[(*index)] = i;
}
}
if(i < (strLen-patLen)) { //find hash value for next window
strHash = (MAXCHAR*(strHash - mainString[i]*h) + mainString[i+patLen])%prime;
if(strHash < 0) {
strHash += prime; //when hash value is negative, make it positive
}
}
}
}
int main() {
string mainString = "ABAAABCDBBABCDDEBCABC";
string pattern = "ABC";
int locArray[mainString.size()];
int prime = 101;
int index = -1;
rabinKarpSearch(mainString, pattern, prime, locArray, &index);
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}输出结果
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18