Thuật toán Boyer Moore

Đây là một cách tiếp cận khác của Thuật toán Boyer Moore. Đôi khi nó được gọi là phương pháp Heuristic Hậu tố Tốt. Đối với trường hợp này, một bảng tiền xử lý được tạo dưới dạng bảng hậu tố. Trong quy trình này, chuỗi con hoặc mẫu được tìm kiếm từ ký tự cuối cùng của mẫu. Khi một chuỗi con của chuỗi chính khớp với một chuỗi con của mẫu, nó sẽ di chuyển để tìm các lần xuất hiện khác của chuỗi con đã khớp. Nó cũng có thể di chuyển để tìm tiền tố của mẫu là hậu tố của chuỗi chính. Nếu không, nó sẽ di chuyển toàn bộ chiều dài của mẫu.

Đầu vào và Đầu ra

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

Thuật toán

fullSuffixMatch (shiftArray, borderArray, mẫu)

Đầu vào - Mảng để lưu trữ các vị trí thay đổi, mảng đường viền và mẫu để tìm kiếm.

Đầu ra - Điền vào mảng shift và mảng đường viền.

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

partSuffixMatch (shiftArray, borderArray, pattern)

Đầu vào− Mảng để lưu trữ các vị trí thay đổi, mảng đường viền và mẫu để tìm kiếm.

Đầu ra - Điền vào mảng shift và mảng đường viền.

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 (văn bản, mẫu)

Đầu vào: Văn bản chính và mẫu sẽ được tìm kiếm

Đầu ra - Các chỉ mục nơi mẫu được tìm thấy

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

Ví dụ

#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) {
      //search right when (i-1)th and (j-1)th item are not same
      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;
    }
}

Đầu ra

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18