String Hashing

String Hashing เป็นเทคนิคที่ใช้แปลง string เป็นตัวเลข (hash value) เพื่อให้สามารถเปรียบเทียบ string ได้อย่างรวดเร็วใน $O(1)$

แนวคิดหลัก

แปลง string $s$ ให้เป็นตัวเลขโดยใช้สูตร:

$$H(s) = (s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + \ldots + s_{n-1} \cdot p^0) \mod m$$

โดยที่:

• $p$ = base (มักใช้ 31 หรือ 37)
• $m$ = modulo (มักใช้ค่าเฉพาะขนาดใหญ่)
• $s_i$ = ค่า ASCII ของตัวอักษรตำแหน่ง $i$

Polynomial Rolling Hash

เพื่อคำนวณ hash ของ substring ใดๆ ใน $O(1)$ เราต้อง precompute prefix hash:

$$prefix[i] = s_0 \cdot p^{i-1} + s_1 \cdot p^{i-2} + \ldots + s_{i-1}$$

Hash ของ substring $s[l..r]$:

$$H(s[l..r]) = prefix[r+1] - prefix[l] \cdot p^{r-l+1}$$

Implementation

const long long MOD = 1e9 + 7;
const long long BASE = 31;

struct StringHash {
    vector<long long> h, p;
    int n;
    
    StringHash(const string& s) {
        n = s.size();
        h.resize(n + 1);
        p.resize(n + 1);
        
        p[0] = 1;
        h[0] = 0;
        
        for (int i = 0; i < n; i++) {
            p[i + 1] = (p[i] * BASE) % MOD;
            h[i + 1] = (h[i] * BASE + (s[i] - 'a' + 1)) % MOD;
        }
    }
    
    // Get hash of s[l..r] (0-indexed, inclusive)
    long long getHash(int l, int r) {
        long long res = (h[r + 1] - h[l] * p[r - l + 1] % MOD + MOD) % MOD;
        return res;
    }
    
    // Compare s[l1..r1] with s[l2..r2]
    bool compare(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

Double Hashing

เพื่อลดโอกาสเกิด collision ใช้ 2 hash functions พร้อมกัน:

struct DoubleHash {
    StringHash h1, h2;
    
    DoubleHash(const string& s) : h1(s, 31, 1e9+7), h2(s, 37, 1e9+9) {}
    
    pair<long long, long long> getHash(int l, int r) {
        return {h1.getHash(l, r), h2.getHash(l, r)};
    }
};

ตัวอย่างการใช้งาน

1. นับ Distinct Substrings ความยาว K

int countDistinct(const string& s, int k) {
    StringHash sh(s);
    set<long long> seen;
    
    for (int i = 0; i + k <= s.size(); i++) {
        seen.insert(sh.getHash(i, i + k - 1));
    }
    
    return seen.size();
}

2. Pattern Matching (Rabin-Karp)

vector<int> rabinKarp(const string& text, const string& pattern) {
    StringHash textHash(text);
    StringHash patternHash(pattern);
    
    vector<int> matches;
    long long patHash = patternHash.getHash(0, pattern.size() - 1);
    
    for (int i = 0; i + pattern.size() <= text.size(); i++) {
        if (textHash.getHash(i, i + pattern.size() - 1) == patHash) {
            matches.push_back(i);
        }
    }
    
    return matches;
}

Complexity

Operation	Time	Space
Preprocessing	$O(n)$	$O(n)$
Query hash	$O(1)$	-
Compare substrings	$O(1)$	-

Tips

1. ใช้ Double Hashing เพื่อลด collision
2. เลือก base และ mod ที่เหมาะสม - base ควรมากกว่าขนาด alphabet, mod ควรเป็นจำนวนเฉพาะขนาดใหญ่
3. ระวัง overflow - ใช้ unsigned long long หรือ __int128
4. Birthday Paradox - โอกาส collision เพิ่มขึ้นเมื่อมี hash values มาก