ฮิวริสติกตัวละครไม่ดี

วิธีฮิวริสติกอักขระที่ไม่ดีเป็นหนึ่งในแนวทางของอัลกอริทึม Boyer Moore อีกวิธีหนึ่งคือ Good Suffix Heuristic ในวิธีนี้ เราจะพยายามค้นหาอักขระที่ไม่ถูกต้อง ซึ่งหมายถึงอักขระของสตริงหลักซึ่งไม่ตรงกับรูปแบบ เมื่อความไม่ตรงกันเกิดขึ้น เราจะเปลี่ยนรูปแบบทั้งหมดจนกว่ารูปแบบที่ไม่ตรงกันจะกลายเป็นการจับคู่ มิฉะนั้น รูปแบบจะเคลื่อนผ่านอักขระที่ไม่ดี

ที่นี่เวลาที่ความซับซ้อนคือ O(m/n) สำหรับกรณีที่ดีที่สุดและ O(mn) สำหรับกรณีที่เลวร้ายที่สุด โดยที่ n คือความยาวของข้อความและ m คือความยาวของรูปแบบ

อินพุตและเอาต์พุต

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

อัลกอริทึม

อักขระที่ไม่ดีHeuristic(รูปแบบ, ตัวละครไม่ดี)

อินพุต - รูปแบบซึ่งจะถูกค้นหาอาร์เรย์อักขระที่ไม่ถูกต้องเพื่อจัดเก็บตำแหน่ง

ผลลัพธ์: กรอกอาร์เรย์อักขระที่ไม่ถูกต้องสำหรับใช้ในอนาคต

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(แพทเทิร์น, ข้อความ)

อินพุต - รูปแบบซึ่งจะถูกค้นหาและข้อความหลัก

ผลลัพธ์ - ตำแหน่งที่พบรูปแบบ

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

ตัวอย่าง

#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;
   }
}

ผลลัพธ์

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