이것은 문자열 매칭을 위한 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