बैड कैरेक्टर यूरिस्टिक

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

यहां बेस्ट केस के लिए टाइम कॉम्प्लेक्सिटी O(m/n) है और सबसे खराब केस के लिए O(mn), जहां n टेक्स्ट की लंबाई है और m पैटर्न की लंबाई है।

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

इनपुट: मेन स्ट्रिंग: "ABAAABCDBBABCDDEBCABC", पैटर्न "ABC"
आउटपुट: पैटर्न मिला स्थिति: 4
पैटर्न मिला स्थिति: 10
पैटर्न मिला स्थिति: 18

एल्गोरिदम

badCharacterHeuristic(pattern, 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(pattern, text)

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

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

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
    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(); // पैटर्न की लंबाई ढूंढें
    for(int i = 0; i < MAXCHAR; i++)
        badCharacter[i] = -1; // सभी कैरेक्टर डिस्टेंस को -1 पर सेट करें
    for(int i = 0; i < n; i++) {
        badCharacter[(int)pattern[i]] = i; // ऐरे में कैरेक्टर की स्थिति सेट करें।
    }
}

void searchPattern(string mainString, string pattern, int *array, int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int badCharacter[MAXCHAR]; // बैड कैरेक्टर पोजीशन के लिए ऐरे बनाएं
    badCharacterHeuristic(pattern, badCharacter); // बैड कैरेक्टर ऐरे भरें
    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;
            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