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