文字列照合のためのBitapアルゴリズムを実装するC++プログラム

これは、文字列照合用のBitapアルゴリズムを実装するためのC++プログラムです。アルゴリズムは、特定のテキストに特定のパターンと「ほぼ等しい」サブストリングが含まれているかどうかを示します。ここで、おおよその等式はレーベンシュタイン距離で定義されます。サブストリングとパターンが互いに特定の距離k内にある場合は、それらが等しいアルゴリズム。まず、パターンの要素ごとに1ビットを含むビットマスクのセットを事前に計算します。そのため、ほとんどの作業をビット単位の演算で実行できます。これは非常に高速です。

アルゴリズム

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