ওয়াইল্ডকার্ড প্যাটার্ন ম্যাচিং

এই সমস্যার জন্য, একটি প্রধান স্ট্রিং এবং আরেকটি ওয়াইল্ডকার্ড প্যাটার্ন দেওয়া হয়েছে৷ এই অ্যালগরিদমে, ওয়াইল্ডকার্ড প্যাটার্ন মূল পাঠ্যের সাথে মিলছে কিনা তা পরীক্ষা করবে।

ওয়াইল্ডকার্ড প্যাটার্নে অক্ষর বা '*' বা '?' চিহ্ন থাকতে পারে। '?' একটি একক অক্ষর মেলানোর জন্য ব্যবহার করা হয় এবং '*' ব্যবহার করা হয় খালি স্থান সহ অক্ষরের ক্রম মেলানোর জন্য।

যখন অক্ষরটি '*' হয়:আমরা তারকা চরিত্রটিকে উপেক্ষা করতে পারি এবং প্যাটার্নের পরবর্তী অক্ষরগুলি পরীক্ষা করতে যেতে পারি।

যখন পরবর্তী অক্ষরটি '?' হয়, তখন আমরা পাঠ্যের বর্তমান অক্ষরটিকে উপেক্ষা করতে পারি এবং প্যাটার্ন এবং পাঠ্যে পরবর্তী অক্ষরটি পরীক্ষা করতে পারি।

যখন প্যাটার্ন অক্ষরটি '*' এবং '?' ব্যতীত অন্য হয়, তখন যদি প্যাটার্ন এবং পাঠ্যের বর্তমান অক্ষর মিলে যায়, তবে কেবলমাত্র আরও এগিয়ে যান।

ইনপুট এবং আউটপুট

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.