सी ++ प्रोग्राम स्ट्रिंग मिलान के लिए बिटैप एल्गोरिथम को लागू करने के लिए

स्ट्रिंग मिलान के लिए बिटैप एल्गोरिदम को लागू करने के लिए यह एक सी ++ प्रोग्राम है। एल्गोरिथम बताता है कि क्या किसी दिए गए टेक्स्ट में एक सबस्ट्रिंग है जो किसी दिए गए पैटर्न के लिए "लगभग बराबर" है, जहां लेवेनशेटिन दूरी के संदर्भ में अनुमानित समानता को परिभाषित किया गया है - यदि सबस्ट्रिंग और पैटर्न एक दूसरे के दिए गए दूरी के भीतर हैं, तो इसके अनुसार एल्गोरिदम वे बराबर हैं। यह पैटर्न के प्रत्येक तत्व के लिए एक बिट युक्त बिटमास्क के एक सेट को प्रीकंप्यूट करके शुरू होता है। इसलिए हम अधिकांश कार्य बिटवाइज़ संचालन के साथ करने में सक्षम हैं, जो बहुत तेज़ हैं।

एल्गोरिदम

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