Properties of String Hashing

• Different hash values guarantee different strings.
• Identical hash values don't guarantee identical strings (though probability is high).

Modulus Selection

Prime moduli are preferable based on number theory. For example, (ax + b) mod p distributes with interval gcd(a, p). The modulus must prevent overflow in 64-bit integers, typically requiring two moduli. Common choices: 1,000,000,123 and 1,000,000,403.

Base Selection

The base should exceed the character set size (typically >256 for ASCII). Random selection within bounds is acceptable.

Dual Hashing

To mitigate birthday attacks, dual hashing with different parameters is recommended. Using 64-bit integers during computation simplifies implementation.

const int MAXN = 200005;
const int HASH_COUNT = 2;
const int BASES[HASH_COUNT] = {91138233, 97266353};
const int MODS[HASH_COUNT] = {1000000007, 1000000009};

long long powers[HASH_COUNT][MAXN], invPowers[HASH_COUNT][MAXN];
long long forwardHash[HASH_COUNT][MAXN], backwardHash[HASH_COUNT][MAXN];

long long fastExponentiation(long long base, long long exponent, int modulus) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

void initializeHashing() {
    for (int hashIdx = 0; hashIdx < HASH_COUNT; ++hashIdx) {
        powers[hashIdx][0] = 1;
        for (int i = 1; i < MAXN; ++i) {
            powers[hashIdx][i] = (powers[hashIdx][i-1] * BASES[hashIdx]) % MODS[hashIdx];
        }
        
        invPowers[hashIdx][MAXN-1] = fastExponentiation(
            powers[hashIdx][MAXN-1], MODS[hashIdx]-2, MODS[hashIdx]
        );
        
        for (int i = MAXN-1; i > 0; --i) {
            invPowers[hashIdx][i-1] = (invPowers[hashIdx][i] * BASES[hashIdx]) % MODS[hashIdx];
        }
    }
}

void computeHashes(const std::string& input) {
    std::string processed = " " + input;
    int length = processed.size();
    
    for (int hashIdx = 0; hashIdx < HASH_COUNT; ++hashIdx) {
        for (int i = 1; i < length; ++i) {
            forwardHash[hashIdx][i] = (
                forwardHash[hashIdx][i-1] * BASES[hashIdx] + processed[i]
            ) % MODS[hashIdx];
            
            backwardHash[hashIdx][i] = (
                backwardHash[hashIdx][i-1] + processed[i] * powers[hashIdx][i-1]
            ) % MODS[hashIdx];
        }
    }
}

std::array<long long, 2> getForwardHash(int left, int right) {
    std::array<long long, 2> result;
    for (int hashIdx = 0; hashIdx < HASH_COUNT; ++hashIdx) {
        result[hashIdx] = (
            forwardHash[hashIdx][right] - 
            forwardHash[hashIdx][left-1] * powers[hashIdx][right-left+1] % MODS[hashIdx] + 
            MODS[hashIdx]
        ) % MODS[hashIdx];
    }
    return result;
}

std::array<long long, 2> getBackwardHash(int left, int right) {
    std::array<long long, 2> result;
    for (int hashIdx = 0; hashIdx < HASH_COUNT; ++hashIdx) {
        result[hashIdx] = (
            (backwardHash[hashIdx][right] - backwardHash[hashIdx][left-1] + MODS[hashIdx]) * 
            invPowers[hashIdx][left-1]
        ) % MODS[hashIdx];
    }
    return result;
}

Hashing Formulas

For string s with character values c[i], prefix hash: hash(x) = Σ(i=1 to x) c[i] * b^(x-i)

Forward Hashing (Decreasing Powers)

h[n] = c[1] * b^(n-1) + c[2] * b^(n-2) + ... + c[n]
h[n] = h[n-1] * b + c[n]
h[l,r] = h[r] - h[l-1] * b^(r-l+1)

Backward Hashing (Increasing Powers)

h[n] = c[1] + c[2] * b + ... + c[n] * b^(n-1)
h[n] = h[n-1] + c[n] * b^(n-1)
h[l,r] = (h[r] - h[l-1]) * inv[b^(l-1)]

Common Applications

Pattern Matching

Count occurrences of pattern in text:

int countOccurrences(const std::string& text, const std::string& pattern) {
    int count = 0;
    int textLen = text.length();
    int patternLen = pattern.length();
    
    computeHashes(text + "#" + pattern);
    auto patternHash = getForwardHash(textLen + 2, textLen + patternLen + 1);
    
    for (int i = 1; i <= textLen - patternLen + 1; ++i) {
        if (getForwardHash(i, i + patternLen - 1) == patternHash) {
            count++;
        }
    }
    return count;
}

Palindrome Detection in O(1)

Check if substring s[l..r] is palindrome by comparing forward and backward hashes:

bool isPalindrome(int left, int right) {
    return getForwardHash(left, right) == getBackwardHash(left, right);
}

Approximate String Matching

Pattern matching with up to k mismatches using binary search on LCP:

int longestCommonPrefix(int pos1, int pos2, int maxLength) {
    int low = 0, high = maxLength;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (getForwardHash(pos1, pos1 + mid - 1) == getForwardHash(pos2, pos2 + mid - 1)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

bool approximateMatch(const std::string& text, const std::string& pattern, int k) {
    int mismatches = 0;
    int textPos = 0, patternPos = 0;
    int patternLen = pattern.length();
    
    while (patternPos < patternLen) {
        int matchLen = longestCommonPrefix(textPos + 1, patternPos + 1, 
                                          patternLen - patternPos);
        
        if (matchLen == patternLen - patternPos) return true;
        
        textPos += matchLen + 1;
        patternPos += matchLen + 1;
        mismatches++;
        
        if (mismatches > k) return false;
    }
    return mismatches <= k;
}

Optimization with Hash Keys

Map Optimization

Using hash values instead of strings as map keys reduces complexity from O(total string length) to O(n) for n operations.

Distinct Substrings Count

int countDistinctSubstrings(const std::string& s) {
    int n = s.length();
    std::unordered_set<long long> distinctHashes;
    
    for (int len = 1; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            auto hash = getForwardHash(i + 1, i + len);
            distinctHashes.insert(hash[0] * 1000000009LL + hash[1]);
        }
    }
    return distinctHashes.size();
}