Thuật toán Bitap (Shift-And) tìm kiếm chuỗi xấp xỉ trong C++

Bitap (Bit-parallel approximate string matching) dùng bitmask để tìm mẫu trong văn bản, cho phép sai số Levenshtein distance ≤ k. Cài đặt chính xác (k=0) dùng bitwise cực nhanh.

Ý tưởng (exact matching)

• Tiền tính bitmask mask[c] cho mỗi ký tự: bit i = 0 nếu pattern[i] == c, ngược lại 1.
• Biến trạng thái R ban đầu = ~1 (bit 0 = 0).
• Duyệt văn bản: R = (R | mask[text[i]]) << 1.
• Nếu bit m của R = 0 → tìm thấy kết thúc tại vị trí i.

Ví dụ minh họa

#include <iostream>
#include <string>
#include <map>
using namespace std;

int bitap_search(const string &text, const string &pat) {
    int m = pat.size();
    if (m == 0 || m > 63) return -1;
    long mask[256];
    for (int i=0; i<256; i++) mask[i] = ~0L;
    for (int i=0; i

Kết quả
Nhap van ban: Tutorialspoint
Nhap mau: point
Tim thay tai vi tri: 9