এই সমস্যায় একটি মূল স্ট্রিং এবং একটি ওয়াইল্ডকার্ড প্যাটার্ন দেওয়া থাকে। এই অ্যালগরিদমে চেক করা হবে ওয়াইল্ডকার্ড প্যাটার্নটি মূল টেক্সটের সাথে মিলে যাচ্ছে কিনা।
ওয়াইল্ডকার্ড প্যাটার্নে অক্ষর, '*' বা '?' চিহ্ন থাকতে পারে। '?' একক ক্যারেক্টার মিলানোর জন্য ব্যবহৃত হয় এবং '*' খালি স্থানসহ ক্যারেক্টার সিকোয়েন্স মিলানোর জন্য।
- যখন ক্যারেক্টার '*' হয়: তারকা ক্যারেক্টারটি উপেক্ষা করে প্যাটার্নের পরবর্তী ক্যারেক্টার চেক করতে পারি।
- যখন পরবর্তী ক্যারেক্টার '?' হয়, তবে টেক্সটের বর্তমান ক্যারেক্টারটি উপেক্ষা করে প্যাটার্ন এবং টেক্সটের পরবর্তী ক্যারেক্টার চেক করতে পারি।
- যখন প্যাটার্ন ক্যারেক্টার '*' এবং '?' ব্যতীত অন্য কিছু হয়, তবে প্যাটার্ন এবং টেক্সটের বর্তমান ক্যারেক্টার মিললে আগে যেতে পারি।
ইনপুট এবং আউটপুট
ইনপুট: মূল স্ট্রিং এবং ওয়াইল্ডকার্ড প্যাটার্ন। Main String: "Algorithm" Pattern: "A*it?m" আউটপুট: প্যাটার্ন মিলেছে।
অ্যালগরিদম
wildcardMatch(text, pattern)
ইনপুট: মূল টেক্সট এবং প্যাটার্ন।
আউটপুট: মূল টেক্সটের জন্য ওয়াইল্ডকার্ড প্যাটার্ন মিললে true।
শুরু
n := টেক্সটের দৈর্ঘ্য
m := প্যাটার্নের দৈর্ঘ্য
যদি m = 0 হয়, তবে
n = 0 হলে ০ ফেরত দিন, অন্যথায় ১
i := 0, j := 0
i < n পর্যন্ত, করুন
যদি text[i] == pattern[j] হয়, তবে
i ১ বৃদ্ধি করুন
j ১ বৃদ্ধি করুন
অন্যথায় যদি j < m এবং pattern[j] '?' হয়, তবে
i ১ বৃদ্ধি করুন
j ১ বৃদ্ধি করুন
অন্যথায় যদি j < m এবং pattern[j] '*' হয়, তবে
textPointer := i
patPointer := j
j ১ বৃদ্ধি করুন
অন্যথায় যদি patPointer ইতিমধ্যে আপডেটেড থাকে, তবে
j := patPointer + 1
i := textPointer + 1
textPointer ১ বৃদ্ধি করুন
অন্যথায়
ফেরত দিন false
শেষ
j < m এবং pattern[j] = '*' পর্যন্ত, করুন
j ১ বৃদ্ধি করুন
শেষ
যদি j = m হয়, তবে
ফেরত দিন true
ফেরত দিন false
শেষ
উদাহরণ (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.
