나쁜 문자 휴리스틱

나쁜 문자 발견적 방법은 Boyer Moore 알고리즘의 접근 방식 중 하나입니다. 또 다른 접근 방식은 Good Suffix 휴리스틱입니다. 이 방법에서 우리는 패턴과 일치하지 않는 주 문자열의 문자를 의미하는 잘못된 문자를 찾으려고 노력할 것입니다. 불일치가 발생하면 불일치가 일치할 때까지 전체 패턴을 이동합니다. 그렇지 않으면 패턴이 잘못된 문자를 지나 이동합니다.

여기서 시간 복잡도는 최상의 경우 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(패턴, 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(패턴, 텍스트)

입력 - 검색할 패턴과 본문

출력 - 패턴이 발견된 위치

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