문자열 일치를 위한 Bitap 알고리즘을 구현하는 C++ 프로그램

이것은 문자열 매칭을 위한 Bitap 알고리즘을 구현하는 C++ 프로그램입니다. 알고리즘은 주어진 텍스트에 주어진 패턴과 "거의 동일한" 부분 문자열이 포함되어 있는지 여부를 알려줍니다. 여기서 근사 평등은 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