वाइल्डकार्ड पैटर्न मिलान

इस समस्या के लिए, एक मुख्य स्ट्रिंग और एक वाइल्डकार्ड पैटर्न दिया जाता है। इस एल्गोरिदम में, यह जांचेगा कि वाइल्डकार्ड पैटर्न मुख्य टेक्स्ट से मिल रहा है या नहीं।

वाइल्डकार्ड पैटर्न में अक्षर या '*' या '?' प्रतीक हो सकते हैं। '?' का उपयोग एक अक्षर से मिलान के लिए किया जाता है और '*' का उपयोग खाली स्थान सहित अक्षरों के अनुक्रम से मिलान के लिए किया जाता है।

जब कैरेक्टर '*' हो: हम स्टार कैरेक्टर को नजरअंदाज कर सकते हैं और पैटर्न में अगले कैरेक्टर्स की जांच के लिए आगे बढ़ सकते हैं।

जब अगला कैरेक्टर '?' हो, तो हम टेक्स्ट में केवल वर्तमान कैरेक्टर को नजरअंदाज कर सकते हैं, और पैटर्न और टेक्स्ट में अगले कैरेक्टर की जांच कर सकते हैं।

जब पैटर्न कैरेक्टर '*' और '?' के अलावा अन्य हो, तो यदि पैटर्न और टेक्स्ट का वर्तमान कैरेक्टर मिल रहा है, तो केवल आगे बढ़ें।

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

इनपुट: मुख्य स्ट्रिंग और वाइल्डकार्ड पैटर्न
मुख्य स्ट्रिंग "Algorithm"
पैटर्न "A*it?m"

आउटपुट: पैटर्न मिल गया।

एल्गोरिदम

wildcardMatch(text, pattern)

इनपुट: मुख्य टेक्स्ट और पैटर्न
आउटपुट: सत्य जब मुख्य टेक्स्ट के लिए वाइल्डकार्ड पैटर्न मिलान हो

शुरुआत
    n := टेक्स्ट की लंबाई
    m := पैटर्न की लंबाई
    यदि m = 0, तो
        वापस 0 यदि n = 0, अन्यथा वापस 1
    i := 0, j := 0
    जब तक i < n, करें
        यदि text[i] == pattern[i], तो
            i को 1 से बढ़ाएं
            j को 1 से बढ़ाएं
        अन्यथा यदि j < m और pattern[j] ? है, तो
            i को 1 से बढ़ाएं
            j को 1 से बढ़ाएं
        अन्यथा यदि j < m और pattern[j] * प्रतीक है, तो
            textPointer := i
            patPointer := j
            j को 1 से बढ़ाएं
        अन्यथा यदि patPointer पहले से अपडेट है, तो
            j := patPointer + 1
            i := textPointer + 1
            textPointer को 1 से बढ़ाएं
        अन्यथा
            वापस असत्य
    पूर्ण
    जब तक j < m और pattern[j] = * प्रतीक, करें
        j को 1 से बढ़ाएं
    पूर्ण
    यदि j = m, तो
        वापस सत्य
    वापस असत्य
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

bool wildcardMatch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    
    if (m == 0)
        return (n == 0);
    
    int i = 0, j = 0, textPointer = -1, pattPointer = -1;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++; j++;
        } else if (j < m && pattern[j] == '?') {
            i++; j++;
        } else if (j < m && pattern[j] == '*') {
            textPointer = i;
            pattPointer = j;
            j++;
        } else if (pattPointer != -1) {
            j = pattPointer + 1;
            i = textPointer + 1;
            textPointer++;
        } else
            return false;
    }
    
    while (j < m && pattern[j] == '*')
        j++;
    
    if (j == m)
        return true;
    
    return false;
}

int main() {
    string text, pattern;
    cout << "Enter Text: "; cin >> text;
    cout << "Enter wildcard pattern: "; cin >> pattern;
    
    if (wildcardMatch(text, pattern))
        cout << "Pattern Matched." << endl;
    else
        cout << "Pattern is not matched" << endl;
}

आउटपुट

Enter Text: Algorithm
Enter wildcard pattern: A*it?m
Pattern Matched.