博耶摩尔算法

这是博耶摩尔算法的另一种方法。有时将其称为“良好后缀启发式”方法。对于这种情况，将创建一个预处理表作为后缀表。在此过程中，从模式的最后一个字符搜索子字符串或模式。当主字符串的子字符串与模式的子字符串匹配时，它将移动以查找匹配子字符串的其他出现。它还可以移动以找到模式的前缀，该模式是主字符串的后缀。否则，它将移动图案的整个长度。

输入输出

Input:
Main String: “ABAAABCDBBABCDDEBCABC”, Pattern: “ABC”
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

算法

fullSuffixMatch(shiftArray,borderArray,pattern)

输入-数组以存储班次位置，边框数组和要搜索的图案。

输出-填充shift数组和border数组。

Begin
   n := pattern length
   j := n
   j := n+1
   borderArray[i] := j

   while i > 0, do
      while j <= n AND pattern[i-1] ≠ pattern[j-1], do
         if shiftArray[j] = 0, then
            shiftArray[j] := j-i;
         j := borderArray[j];
      done

      decrease i and j by 1
      borderArray[i] := j
   done
End

 partialSuffixMatch(shiftArray,borderArray,pattern)

输入-用于存储班次位置的数组，边界数组和要搜索的样式。

输出-填充shift数组和border数组。

Begin
   n := pattern length
   j := borderArray[0]

   for index of all characters ‘i’ of pattern, do
      if shiftArray[i] = 0, then
         shiftArray[i] := j
      if i = j then
         j := borderArray[j]
   done
End

searchPattern（文字，图案）

输入： 将要搜索的主要文本和样式

输出- 找到模式的索引

Begin
   patLen := pattern length
   strLen := text size

   for all entries of shiftArray, do
      set all entries to 0
   done

   call fullSuffixMatch(shiftArray, borderArray, pattern)
   call partialSuffixMatch(shiftArray, borderArray, pattern)
   shift := 0

   while shift <= (strLen - patLen), do
      j := patLen -1
      while j >= 0 and pattern[j] = text[shift + j], do
         decrease j by 1
      done

      if j < 0, then
         print the shift as, there is a match
         shift := shift + shiftArray[0]
      else
         shift := shift + shiftArray[j+1]
   done
End

示例

#include<iostream>
using namespace std;

void fullSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
   int n = pattern.size();       //find length of pattern
   int i = n;
   int j = n+1;
   borderArr[i] = j;

   while(i > 0) {
      //当第(i-1)和第(j-1)项不相同时向右搜索
      while(j <= n && pattern[i-1] != pattern[j-1] ) {
         if(shiftArr[j] == 0)
            shiftArr[j] = j-i;     //shift pattern from i to j
         j = borderArr[j];       //update border
      }
      i--;
      j--;
      borderArr[i] = j;
   }  
}

void partialSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
   int n = pattern.size();    //find length of pattern
   int j;
   j = borderArr[0];

   for(int i = 0; i<n; i++) {
      if(shiftArr[i] == 0)
         shiftArr[i] = j;        //when shift is 0, set shift to border value
         if(i == j)
            j = borderArr[j];    //update border value
   }
}

void searchPattern(string mainString, string pattern, int array[], int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();
   int borderArray[patLen+1];
   int shiftArray[patLen + 1];

   for(int i = 0; i<=patLen; i++) {
      shiftArray[i] = 0;     //set all shift array to 0
   }

   fullSuffixMatch(shiftArray, borderArray, pattern);
   partialSuffixMatch(shiftArray, borderArray, pattern);
   int shift = 0;

   while(shift <= (strLen - patLen)) {
      int j = patLen - 1;
      while(j >= 0 && pattern[j] == mainString[shift+j]) {
         j--;         //reduce j when pattern and main string character is matching
      }

      if(j < 0) {
         (*index)++;
         array[(*index)] = shift;
         shift += shiftArray[0];
      }else {
          shift += shiftArray[j+1];
      }
   }
}

int main() {
   string mainString = "ABAAABCDBBABCDDEBCABC";
   string pattern = "ABC";
   int locArray[mainString.size()];
   int index = -1;
   searchPattern(mainString, pattern, 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