悪いキャラクターのヒューリスティック

悪い文字のヒューリスティック手法は、ボイヤームーアアルゴリズムのアプローチの1つです。もう1つのアプローチは、GoodSuffixHeuristicです。この方法では、パターンと一致しないメイン文字列の文字を意味する不正な文字を見つけようとします。不一致が発生した場合は、不一致が一致するまでパターン全体をシフトします。一致しない場合は、パターンが不良文字を超えて移動します。

ここで、時間計算量は、最良の場合は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

アルゴリズム

badCharacterHeuristic（pattern、badCharacterArray）

入力- 検索されるパターン、場所を格納するための不正な文字配列

出力： 将来の使用のために不良文字配列を埋める

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（pattern、text）

入力- 検索されるパターンと本文

出力- パターンが見つかった場所

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