খারাপ চরিত্র হিউরিস্টিক

খারাপ চরিত্র হিউরিস্টিক পদ্ধতি হল বয়য়ার মুর অ্যালগরিদমের পন্থাগুলির মধ্যে একটি৷ আরেকটি পদ্ধতি হল গুড সাফিক্স হিউরিস্টিক। এই পদ্ধতিতে আমরা একটি খারাপ অক্ষর খুঁজে বের করার চেষ্টা করব, মানে মেইন স্ট্রিংয়ের একটি অক্ষর, যা প্যাটার্নের সাথে মিলছে না। অমিলটি ঘটলে, অমিলটি একটি মিল না হওয়া পর্যন্ত আমরা সম্পূর্ণ প্যাটার্নটি স্থানান্তরিত করব, অন্যথায়, প্যাটার্নটি খারাপ অক্ষরকে অতিক্রম করবে৷

এখানে সময়ের জটিলতা হল 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

অ্যালগরিদম

bad CharacterHeuristic(প্যাটার্ন, 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

সার্চ প্যাটার্ন(প্যাটার্ন, টেক্সট)

ইনপুট −৷ প্যাটার্ন, যা অনুসন্ধান করা হবে এবং মূল পাঠ্য

আউটপুট − অবস্থান যেখানে প্যাটার্ন পাওয়া যায়

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