বোয়ার মুর অ্যালগরিদম

এটি বয়ার মুর অ্যালগরিদমের আরেকটি পদ্ধতি। কখনও কখনও এটি ভাল প্রত্যয় হিউরিস্টিক পদ্ধতি বলা হয়। এই ক্ষেত্রে, একটি প্রিপ্রসেসিং টেবিল প্রত্যয় টেবিল হিসাবে তৈরি করা হয়। এই পদ্ধতিতে, প্যাটার্নের শেষ অক্ষর থেকে সাবস্ট্রিং বা প্যাটার্ন অনুসন্ধান করা হয়। যখন প্রধান স্ট্রিংয়ের একটি সাবস্ট্রিং প্যাটার্নের একটি সাবস্ট্রিংয়ের সাথে মেলে, তখন এটি মিলে যাওয়া সাবস্ট্রিংয়ের অন্যান্য ঘটনাগুলি খুঁজে বের করতে চলে যায়। এটি প্যাটার্নের একটি উপসর্গ খুঁজে পেতেও যেতে পারে যা প্রধান স্ট্রিংয়ের একটি প্রত্যয়। অন্যথায়, এটি প্যাটার্নের পুরো দৈর্ঘ্যকে সরিয়ে দেয়।

ইনপুট এবং আউটপুট

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

অ্যালগরিদম

fullSuffixMatch(shiftArray, borderArray, pattern)

ইনপুট - স্থানান্তর স্থান সংরক্ষণের জন্য অ্যারে, সীমানা অ্যারে এবং অনুসন্ধানের প্যাটার্ন৷

আউটপুট - শিফট অ্যারে এবং বর্ডার অ্যারে পূরণ করুন।

Begin
   n := pattern length
   j := n
   j := n+1
   borderArray[i] := j

   while i > 0, do
      while j <= n AND pattern[i-1] ≠ pattern[j-1], do
         if shiftArray[j] = 0, then
            shiftArray[j] := j-i;
         j := borderArray[j];
      done

      decrease i and j by 1
      borderArray[i] := j
   done
End

partialSuffixMatch(shiftArray, borderArray, pattern)

ইনপুট− স্থানান্তর স্থান সংরক্ষণের জন্য অ্যারে, সীমানা অ্যারে এবং অনুসন্ধানের প্যাটার্ন৷

আউটপুট - শিফট অ্যারে এবং বর্ডার অ্যারে পূরণ করুন।

Begin
   n := pattern length
   j := borderArray[0]

   for index of all characters ‘i’ of pattern, do
      if shiftArray[i] = 0, then
         shiftArray[i] := j
      if i = j then
         j := borderArray[j]
   done
End

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

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

আউটপুট - সূচী যেখানে প্যাটার্ন পাওয়া যায়

Begin
   patLen := pattern length
   strLen := text size

   for all entries of shiftArray, do
      set all entries to 0
   done

   call fullSuffixMatch(shiftArray, borderArray, pattern)
   call partialSuffixMatch(shiftArray, borderArray, pattern)
   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
         shift := shift + shiftArray[0]
      else
         shift := shift + shiftArray[j+1]
   done
End

উদাহরণ

#include<iostream>
using namespace std;

void fullSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
   int n = pattern.size();       //find length of pattern
   int i = n;
   int j = n+1;
   borderArr[i] = j;

   while(i > 0) {
      //search right when (i-1)th and (j-1)th item are not same
      while(j <= n && pattern[i-1] != pattern[j-1] ) {
         if(shiftArr[j] == 0)
            shiftArr[j] = j-i;     //shift pattern from i to j
         j = borderArr[j];       //update border
      }
      i--;
      j--;
      borderArr[i] = j;
   }  
}

void partialSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
   int n = pattern.size();    //find length of pattern
   int j;
   j = borderArr[0];

   for(int i = 0; i<n; i++) {
      if(shiftArr[i] == 0)
         shiftArr[i] = j;        //when shift is 0, set shift to border value
         if(i == j)
            j = borderArr[j];    //update border value
   }
}

void searchPattern(string mainString, string pattern, int array[], int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();
   int borderArray[patLen+1];
   int shiftArray[patLen + 1];

   for(int i = 0; i<=patLen; i++) {
      shiftArray[i] = 0;     //set all shift array to 0
   }

   fullSuffixMatch(shiftArray, borderArray, pattern);
   partialSuffixMatch(shiftArray, borderArray, pattern);
   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;
         shift += shiftArray[0];
      }else {
          shift += shiftArray[j+1];
      }
   }
}

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