Nhân vật xấu Heuristic

Phương pháp heuristic ký tự xấu là một trong những cách tiếp cận của Thuật toán Boyer Moore. Một cách tiếp cận khác là Heuristic Hậu tố Tốt. Trong phương pháp này, chúng tôi sẽ cố gắng tìm một ký tự xấu, có nghĩa là một ký tự của chuỗi chính, không khớp với mẫu. Khi sự không khớp đã xảy ra, chúng tôi sẽ thay đổi toàn bộ mẫu cho đến khi sự không khớp trở thành một kết quả phù hợp, nếu không, mẫu sẽ di chuyển qua ký tự xấu.

Ở đây độ phức tạp về thời gian là O (m / n) đối với trường hợp tốt nhất và O (mn) đối với trường hợp xấu nhất, trong đó n là độ dài của văn bản và m là độ 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

badCharacterHeuristic (mẫu, badCharacterArray)

Đầu vào - mẫu, sẽ được tìm kiếm, mảng ký tự xấu để lưu trữ vị trí

Đầu ra: Điền vào mảng ký tự xấu để sử dụng trong tương lai

Begin
   n := pattern length
   for all entries of badCharacterArray, do
      set all entries to -1
   done

   for all characters of the pattern, do
      set last position of each character in badCharacterArray.
   done
End

searchPattern (mẫu, văn bản)

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

Đầu ra - các vị trí mà mẫu được tìm thấy

Begin
   patLen := length of pattern
   strLen := length of text.
   call badCharacterHeuristic(pattern, badCharacterArray)
   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
         if shift + patLen < strLen, then
            shift:= shift + patLen – badCharacterArray[text[shift + patLen]]
         else
            increment shift by 1
      else
         shift := shift + max(1, j-badCharacterArray[text[shift+j]])
   done
End

Ví dụ

#include<iostream>
#define MAXCHAR 256
using namespace std;

int maximum(int data1, int data2) {
   if(data1 > data2)
      return data1;
   return data2;
}

void badCharacterHeuristic(string pattern, int badCharacter[MAXCHAR]) {
   int n = pattern.size();                   //find length of pattern
   for(int i = 0; i<MAXCHAR; i++)
      badCharacter[i] = -1;                 //set all character distance as -1

   for(int i = 0; i < n; i++) {
      badCharacter[(int)pattern[i]] = i;   //set position of character in the array.
   }  
}

void searchPattern(string mainString, string pattern, int *array, int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();
   int badCharacter[MAXCHAR];           //make array for bad character position
   badCharacterHeuristic(pattern, badCharacter);       //fill bad character array
   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;

         if((shift + patLen) < strLen) {
            shift += patLen - badCharacter[mainString[shift + patLen]];
         }else {
            shift += 1;
         }
      }else {
         shift += maximum(1, j - badCharacter[mainString[shift+j]]);
      }
   }
}

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