बॉयर-मूर एल्गोरिदम

यह बॉयर-मूर एल्गोरिदम का एक अन्य दृष्टिकोण है। कभी-कभी इसे गुड सफिक्स यूरिस्टिक मेथड कहा जाता है। इस मामले में, एक प्रीप्रोसेसिंग टेबल सफिक्स टेबल के रूप में बनाई जाती है। इस प्रक्रिया में, सबस्ट्रिंग या पैटर्न को पैटर्न के अंतिम कैरेक्टर से खोजा जाता है। जब मेन स्ट्रिंग का एक सबस्ट्रिंग पैटर्न के सबस्ट्रिंग से मेल खाता है, तो यह मिले हुए सबस्ट्रिंग की अन्य घटनाओं को खोजने के लिए आगे बढ़ता है। यह मेन स्ट्रिंग के सफिक्स जो पैटर्न का प्रीफिक्स है, को खोजने के लिए भी आगे बढ़ सकता है। अन्यथा, यह पैटर्न की पूरी लंबाई तक मूव करता है।

इनपुट और आउटपुट

इनपुट: मेन स्ट्रिंग: "ABAAABCDBBABCDDEBCABC", पैटर्न: "ABC"
आउटपुट: पैटर्न मिला स्थिति: 4
पैटर्न मिला स्थिति: 10
पैटर्न मिला स्थिति: 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 pattern के सभी कैरेक्टर्स के इंडेक्स 'i' के लिए, do
        if shiftArray[i] = 0, then
            shiftArray[i] := j
        if i = j then
            j := borderArray[j]
        done
    done
End

searchPattern(text, pattern)

इनपुट: मेन टेक्स्ट और पैटर्न, जिसे खोजा जाएगा

आउटपुट: वे इंडेक्स जहां पैटर्न मिला

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
    done
End

उदाहरण

#include <iostream>
using namespace std;

void fullSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
    int n = pattern.size(); // पैटर्न की लंबाई ढूंढें
    int i = n;
    int j = n + 1;
    borderArr[i] = j;
    while(i > 0) {
        // दाईं ओर खोजें जब (i-1)th और (j-1)th आइटम समान नहीं हैं
        while(j <= n && pattern[i-1] != pattern[j-1]) {
            if(shiftArr[j] == 0)
                shiftArr[j] = j - i; // पैटर्न को i से j तक शिफ्ट करें
            j = borderArr[j]; // बॉर्डर अपडेट करें
        }
        i--; j--;
        borderArr[i] = j;
    }
}

void partialSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
    int n = pattern.size(); // पैटर्न की लंबाई ढूंढें
    int j;
    j = borderArr[0];
    for(int i = 0; i < n; i++) {
        if(shiftArr[i] == 0)
            shiftArr[i] = j; // जब शिफ्ट 0 हो, शिफ्ट को बॉर्डर वैल्यू पर सेट करें
        if(i == j)
            j = borderArr[j]; // बॉर्डर वैल्यू अपडेट करें
    }
}

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; // सभी शिफ्ट ऐरे को 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--; // जब पैटर्न और मेन स्ट्रिंग कैरेक्टर मैच कर रहे हों तो 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()];
    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