Bitap Algorithm (Shift-And) สำหรับ String Matching ใน C++

Bitap Algorithm (หรือ Shift-And) ใช้ bitwise operations ทำ string matching รวดเร็วสำหรับ pattern สั้น (≤ 64 chars) และ exact matching

หลักการทำงาน

• Precompute bitmask สำหรับแต่ละตัวอักษรใน pattern
• ใช้ bit vector R ติดตามสถานะการ match
• Shift และ AND ด้วย bitmask สำหรับแต่ละตัวอักษรใน text
• ถ้าบิตที่ m-1 เป็น 0 → พบ match จบที่ตำแหน่งนั้น

รายละเอียด

Pattern length = m, Text length = n

• Bitmask mask[c]: บิตที่ j เป็น 0 ถ้า pattern[j] == c, ไมเช่นนั้นเป็น 1
• State R: เริ่มต้น ~1 (ทุกบิต 1 ยกเว้น LSB)
• Update: R = (R << 1) | mask[text[i]]
• Match: (R & (1 << (m-1))) == 0

ตัวอย่างโค้ด (Exact Matching)

#include <iostream>
#include <string>
#include <vector>
#include <climits>

using namespace std;

// Bitap exact matching (pattern length <= 63 for 64-bit)
int bitapSearch(const string& text, const string& pattern) {
    int m = pattern.length();
    if (m == 0) return -1;
    if (m > 63) {
        cerr << "Pattern too long for 64-bit Bitap (max 63)\n";
        return -1;
    }
    
    // Precompute masks for all possible chars (ASCII 0-255)
    uint64_t mask[256];
    for (int c = 0; c < 256; ++c) mask[c] = ~0ULL;  // All 1s
    
    for (int i = 0; i < m; ++i) {
        mask[static_cast<unsigned char>(pattern[i])] &= ~(1ULL << i);
    }
    
    uint64_t R = ~1ULL;  // ...11110 (LSB = 0)
    
    for (int i = 0; i < text.length(); ++i) {
        unsigned char c = text[i];
        R = (R << 1) | mask[c];
        
        // Check if bit m-1 is 0 (match found ending at i)
        if ((R & (1ULL << (m - 1))) == 0) {
            return i - m + 1;  // Return start position
        }
    }
    return -1;  // Not found
}

int main() {
    string text, pattern;
    
    cout << "Enter text: ";
    getline(cin, text);
    cout << "Enter pattern: ";
    getline(cin, pattern);
    
    int pos = bitapSearch(text, pattern);
    
    if (pos == -1) {
        cout << "No match found\n";
    } else {
        cout << "Pattern found at position: " << pos << endl;
        
        // Show context
        int start = max(0, pos - 10);
        int end = min((int)text.length(), pos + pattern.length() + 10);
        cout << "Context: ..." << text.substr(start, end - start) << "..." << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter text: Tutorialspoint
Enter pattern: point
Pattern found at position: 9
Context: ...Tutorialspoint...

ขยายเป็น Approximate Matching (Fuzzy Search)

Bitap สามารถขยายเป็น **Levenshtein distance ≤ k** ได้ โดยใช้ array ของ state vectors:

// Bitap for k-differences (approximate matching)
vector<int> bitapApproximate(const string& text, const string& pattern, int k) {
    int m = pattern.length();
    if (m > 63) return {};
    
    uint64_t mask[256];
    for (int c = 0; c < 256; ++c) mask[c] = ~0ULL;
    for (int i = 0; i < m; ++i) {
        mask[static_cast<unsigned char>(pattern[i])] &= ~(1ULL << i);
    }
    
    // R[d] = state for edit distance d
    vector<uint64_t> R(k + 1, ~1ULL);
    // Initialize R[d] for d > 0 (allow d deletions at start)
    for (int d = 1; d <= k; ++d) {
        R[d] = (R[d-1] << 1) | ~0ULL;  // Actually more complex...
    }
    
    vector<int> matches;
    for (int i = 0; i < text.length(); ++i) {
        unsigned char c = text[i];
        uint64_t prev = R[0];
        R[0] = (R[0] << 1) | mask[c];
        
        for (int d = 1; d <= k; ++d) {
            uint64_t cur = R[d];
            // Substitution, Insertion, Deletion
            R[d] = ((R[d] << 1) | mask[c]) & (prev << 1) & (R[d-1] << 1) & R[d-1];
            prev = cur;
        }
        
        if ((R[k] & (1ULL << (m - 1))) == 0) {
            matches.push_back(i - m + 1);
        }
    }
    return matches;
}

ข้อดี/ข้อจำกัด

การประยุกต์ใช้

• Text editors: find/replace
• DNA sequence matching (short patterns)
• Virus signature scanning
• Keyboard input prediction
• Regex engines (ส่วนหนึ่ง)

Modern C++: std::string::find

ใน C++17+ std::string::find ใช้ 알고리ทึมที่ optimized แล้ว (มักเป็น Boyer-Moore หรือ Two-Way) ให้ใช้ built-in สำหรับ production code