โปรแกรม C++ เพื่อใช้ Bitap Algorithm สำหรับการจับคู่สตริง

นี่คือโปรแกรม C++ ที่ใช้ Bitap Algorithm สำหรับการจับคู่สตริง อัลกอริธึมบอกว่าข้อความที่กำหนดมีสตริงย่อยที่ "เท่ากับโดยประมาณ" กับรูปแบบที่กำหนดหรือไม่ โดยที่ความเท่าเทียมกันโดยประมาณถูกกำหนดในแง่ของระยะทาง Levenshtein หากสตริงย่อยและรูปแบบอยู่ภายในระยะที่กำหนด 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