বয়ার মূর অ্যালগরিদম-এর একটি অ্যাপ্রোচ হলো গুড সাফিক্স হিউরিস্টিক। এতে একটি প্রিপ্রসেসিং টেবিল (সাফিক্স টেবিল) তৈরি করা হয়। প্যাটার্নটি শেষ ক্যারেক্টার থেকে সার্চ করা হয়। যখন মেন স্ট্রিংয়ের সাবস্ট্রিং প্যাটার্নের সাবস্ট্রিংয়ের সাথে ম্যাকচ করে, তবে অন্য ঘটনার খোঁজা শুরু হয়। এটি প্যাটার্নের প্রিফিক্স (যেটি মেন স্ট্রিংয়ের সাফিক্স) খুঁজতে পারে। অন্যথায় পুরো প্যাটার্নের লেথ만큼 শিফট হয়।
ইনপুট এবং আউটপুট
Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern: "ABC"
Output: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18
অ্যালগরিদম
fullSuffixMatch(shiftArr, borderArr, pattern) - ফুল সাফিক্স ম্যাচের জন্য শিফট ও বর্ডার অ্যারে বানানো
partialSuffixMatch(shiftArr, borderArr, pattern) - পার্শিয়াল সাফিক্স ম্যাচের জন্য শিফট অ্যারে আপডেট
searchPattern(text, pattern) - মূল সার্চ ফাংশন
C++ উদাহরণ
#include <iostream>
using namespace std;
void fullSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
int n = pattern.size(), i = n, j = n+1;
borderArr[i] = j;
while(i > 0) {
while(j <= n && pattern[i-1] != pattern[j-1]) {
if(shiftArr[j] == 0) shiftArr[j] = j - i;
j = borderArr[j];
}
i--; j--; borderArr[i] = j;
}
}
void partialSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
int n = pattern.size(), j = borderArr[0];
for(int i=0; i= 0 && pattern[j] == mainString[shift+j]) j--;
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()], 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
