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

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

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

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

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

जब पैटर्न कैरेक्टर '*' और '?' से इतर हो, तो अगर पैटर्न और टेक्स्ट का मौजूदा कैरेक्टर मेल खा रहा है, तो ही आगे बढ़ें।

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

Input:
The main string and the wildcard pattern.
Main String “Algorithm”
Pattern “A*it?m”
Output:
The pattern matched.

एल्गोरिदम

wildcardMatch(text, pattern)

इनपुट: मुख्य पाठ और पैटर्न।

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

Begin
   n := length of the text
   m := length of pattern

   if m = 0, then
      return 0 if n = 0, otherwise return 1
   i := 0, j := 0

   while i < n, do
      if text[i] == pattern[i], then
         increase i by 1
         increase j by 1
      else if j < m and pattern[j] is ? mark, then
         increase i by 1
         increase j by 1
      else if j < m and pattern[j] is * symbol, then
         textPointer := i
         patPointer := j
         increase j by 1
      else if patPointer is already updated, then
         j := patPointer + 1
         i := textPinter + 1
         increase textPointer by 1
      else
         return false
   done

   while j < m and pattern[j] = * symbol, do
      increase j by 1
   done

   if j = m, then
      return true
   return false
End

उदाहरण

#include<iostream>
using namespace std;

bool wildcardMatch(string text, string pattern) {
   int n = text.size();
   int m = pattern.size();

   if (m == 0)    //when pattern is empty
      return (n == 0);

   int i = 0, j = 0, textPointer = -1, pattPointer = -1;
   while (i < n) {
      if (text[i] == pattern[j]) {    //matching text and pattern characters
         i++;
         j++;
      }else if (j < m && pattern[j] == '?') {    //as ? used for one character
         i++;
         j++;
      }else if (j < m && pattern[j] == '*') {    //as * used for one or more character
         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++;     //j will increase when wildcard is *
   }

   if (j == m) {    //check whether pattern is finished or not
      return true;
   }

   return false;
}

int main() {
   string text;
   string 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.