Chương trình C ++ để triển khai thuật toán bitap để so khớp chuỗi

Đây là một chương trình C ++ để triển khai thuật toán bản đồ bit để đối sánh chuỗi. Thuật toán cho biết liệu một văn bản nhất định có chứa một chuỗi con "xấp xỉ bằng" với một mẫu nhất định hay không, trong đó bình đẳng gần đúng được xác định theo khoảng cách Levenshtein - nếu chuỗi con và mẫu nằm trong khoảng cách k nhất định đối với nhau, thì theo thuật toán chúng bằng nhau. Nó bắt đầu bằng cách tính toán trước một tập hợp các mặt nạ bit chứa một bit cho mỗi phần tử của mẫu. Vì vậy, chúng tôi có thể thực hiện hầu hết công việc bằng các thao tác bitwise, cực kỳ nhanh chóng.

Thuật toán

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

Mã mẫu

#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);
}

Đầu ra

Enter Text:
Tutorialspoint
Enter Pattern:
point

Pattern found at position : 9