यह स्ट्रिंग मैचिंग के लिए बिटैप एल्गोरिदम को लागू करने के लिए एक C++ प्रोग्राम है। एल्गोरिदम बताता है कि क्या दिया गया टेक्स्ट एक सबस्ट्रिंग समाहित करता है जो दिए गए पैटर्न के "लगभग बराबर" है, जहां अनुमानित समानता लेवेनश्टाइन दूरी के संदर्भ में परिभाषित है — यदि सबस्ट्रिंग और पैटर्न एक-दूसरे के दिए गए दूरी k के भीतर हैं, तो एल्गोरिदम के अनुसार वे समान हैं। यह पैटर्न के प्रत्येक एलिमेंट के लिए एक बिट समाहित करने वाले बिटमास्क के सेट को प्रीकंप्यूट करके शुरू होता है। इसलिए हम अधिकांश काम बिटवाइज़ ऑपरेशन्स के साथ कर सकते हैं, जो अत्यंत तेज़ हैं।
एल्गोरिदम
Begin स्ट्रिंग और पैटर्न को इनपुट के रूप में लें। function 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]] 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!";//यदि पैटर्न बहुत लंबा है 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
