স্ট্রিং ম্যাচিংয়ের জন্য বিটাপ অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

স্ট্রিং ম্যাচিংয়ের জন্য বিটাপ অ্যালগরিদম বাস্তবায়নের জন্য এটি একটি C++ প্রোগ্রাম। অ্যালগরিদম বলে যে একটি প্রদত্ত পাঠ্যটিতে একটি সাবস্ট্রিং রয়েছে যা একটি প্রদত্ত প্যাটার্নের "প্রায় সমান", যেখানে আনুমানিক সমতা লেভেনশটাইন দূরত্বের পরিপ্রেক্ষিতে সংজ্ঞায়িত করা হয়েছে — যদি সাবস্ট্রিং এবং প্যাটার্ন একে অপরের একটি নির্দিষ্ট দূরত্ব k এর মধ্যে থাকে, তাহলে অনুযায়ী অ্যালগরিদম তারা সমান। এটি প্যাটার্নের প্রতিটি উপাদানের জন্য একটি বিট ধারণকারী বিটমাস্কের একটি সেট প্রি-কম্পিউটিংয়ের মাধ্যমে শুরু হয়। তাই আমরা বিটওয়াইজ অপারেশনগুলির সাথে বেশিরভাগ কাজ করতে সক্ষম, যেগুলি অত্যন্ত দ্রুত৷

অ্যালগরিদম

Begin
   Take the string and pattern as input.
   function bitmap_search() and it takes argument string text t and string pattern p :
   Initialize the bit array A.
   Initialize the pattern bitmasks, p_mask[300]
   Update the bit array.
   for i = 0 to 299
      p_mask[i] = ~0
   for i = 0 to m-1
      p_mask[p[i]] and= ~(1L left shift i);
   for i = 0 to t.length()-1
      A |= p_mask[t[i]];
      A <<= 1;
   if ((A and (1L left shift m)) == 0
      return i - m + 1
      return -1
End

উদাহরণ কোড

#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!";//if 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);//initialize the position with the function 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