এটি স্ট্রিং ম্যাচিংয়ের জন্য বিট্যাপ অ্যালগরিদম ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম। এই অ্যালগরিদম বলে দেয় যে দিয়ে गये টেক্সটে একটি সাবস্ট্রিং আছে কিনা যা দিয়ে गये প্যাটার্নের সাথে "প্রায় সমান", যেখানে প্রায় সমানতা লেভেনস্টাইন ডিস্ট্যান্স দিয়ে ডিফাইন করা হয় - যদি সাবস্ট্রিং এবং প্যাটার্ন একে অপরের মধ্যে দিয়ে गये দূরত্ব k-এর মধ্যে থাকে, তবে অ্যালগরিদম অনুযায়ী সেগুলো সমান। এটি প্যাটার্নের প্রতিটি এলিমেন্টের জন্য এক বিট ধারণকারী বিটমাস্কের একটি সেট প্রিকম্পিউট করে শুরু করে। তাই আমরা অধিকাংশ কাজ বিটওয়াইজ অপারেশন দিয়ে করতে পারি, যা অত্যন্ত দ্রুত।
অ্যালগরিদম
শুরু
স্ট্রিং এবং প্যাটার্ন ইনপুট নাও।
bitmap_search() ফাংশন যা আর্গুমেন্ট হিসেবে স্ট্রিং টেক্সট t এবং স্ট্রিং প্যাটার্ন p নেয়:
বিট অ্যারে A ইনিশিয়ালাইজ করো।
প্যাটার্ন বিটমাস্ক, p_mask[300] ইনিশিয়ালাইজ করো।
বিট অ্যারে আপডেট করো।
for i = 0 to 299
p_mask[i] = ~0
for i = 0 to m-1
p_mask[p[i]] &= ~(1L << i);
for i = 0 to t.length()-1
A |= p_mask[t[i]];
A <<= 1;
if ((A & (1L << m)) == 0)
return i - m + 1
return -1
শেষউদাহরণ কোড
#include <string>
#include <map>
#include <iostream>
using namespace std;
int bitmap_search(string t, string p) {
int m = p.length();
long p_mask[300];
long A = ~1;
if (m == 0)
return -1;
if (m > 63) {
cout << "Pattern is too long!"; // প্যাটার্ন যদি খুব লম্বা হয়
return -1;
}
for (int i = 0; i <= 299; ++i)
p_mask[i] = ~0;
for (int i = 0; i < m; ++i)
p_mask[p[i]] &= ~(1L << i);
for (int i = 0; i < t.length(); ++i) {
A |= p_mask[t[i]];
A <<= 1;
if ((A & (1L << m)) == 0)
return i - m + 1;
}
return -1;
}
void findPattern(string t, string p) {
int position = bitmap_search(t, p); // bitmap_search ফাংশন দিয়ে পজিশন ইনিশিয়ালাইজ
if (position == -1)
cout << "\nNo Match\n";
else
cout << "\nPattern found at position: " << position;
}
int main(int argc, char **argv) {
cout << "Enter Text:\n";
string t;
cin >> t;
cout << "Enter Pattern:\n";
string p;
cin >> p;
findPattern(t, p);
}আউটপুট
Enter Text: Tutorialspoint Enter Pattern: point Pattern found at position: 9
