Consider the following problem:

Given a string "hello", how would you represent it as a numerical value?

A straightforward approach would be to convert each character to its ASCII value and combine these numbers in some way. For "hello", this might look like 104, 101, 108, 108, 111. But how do we combine these into a single number?

This process of converting a string to a numerical representation is known as string hashing, and the resulting number is called the hash value.

Basic Concepts

Hash Value

A hash value is a numerical representation of a string obtained through a specific mathematical transformation. We'll denote it as H(s) for a string s.

The primary advantage of string hashing is that it allows us to compare strings in constant time O(1) after some preprocessing. Traditional string comparison requires checking each character sequentially, which takes O(n) time where n is the string length.

Base Number

When converting "hello" to numbers, we might combine the ASCII values as follows:

result = 0
result = result * 10 + 104  // 'h'
result = result * 10 + 101  // 'e'
result = result * 10 + 108  // 'l'
result = result * 10 + 108  // 'l'
result = result * 10 + 111  // 'o'

This gives us 104101108108111. But why multiply by 10? Because we're working in base-10 (decimal). In hashing, this mutliplier is called the base number or radix, which we'll denote as B.

The general formula for computing a hash value is:

H(s) = s₁·B^(n-1) + s₂·B^(n-2) + ... + sₙ·B⁰Where s is the string, n is its length, and sᵢ is the numerical value of the i-th character.

Modulo Operation

As strings grow longer, their hash values can become extremely large, potentially exceeding the maximum value of standard data types. To prevent this, we use a modulo operation with a prime number M:

H(s) = (s₁·B^(n-1) + s₂·B^(n-2) + ... + sₙ·B⁰) mod MThis ensures the hash value stays within a manageable range [0, M-1]. However, it introduces the possibility of hash collisions - different strings producing the same hash value.

To minimize collisions, we should choose a large prime number for M. Common choices include 998244353, 19491001, and 1145141.

An alternative approach is to use unsigned 64-bit integers (uint64_t) and let the values naturally overflow, which effectively uses 2^64 as the modulus. This technique, called natural overflow, simplifies implementation but may be less reliable in competitive programming environments.

Implementation

Now let's implemant a string hashing solution. The basic approach is:

1. Compute the hash value for each string
2. Count the number of distinct hash values

To efficiently count distinct values, we can sort the hash values and then count how many times the value changes between consecutive elements.

Implementation with String Input

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const unsigned long long MOD = 212370440130137957; // Large prime modulus
const unsigned long long BASE = 191; // Base for the hash function

// Function to compute hash of a string
unsigned long long computeHash(const string& s) {
    unsigned long long hashValue = 0;
    for (char c : s) {
        hashValue = (hashValue * BASE + c) % MOD;
    }
    return hashValue;
}

int main() {
    int n;
    cin >> n;
    vector<unsigned long=""> hashes(n);
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        hashes[i] = computeHash(s);
    }
    
    // Sort to group identical hashes together
    sort(hashes.begin(), hashes.end());
    
    // Count distinct hashes
    int distinctCount = 1;
    for (int i = 1; i < n; i++) {
        if (hashes[i] != hashes[i-1]) {
            distinctCount++;
        }
    }
    
    cout << distinctCount << endl;
    return 0;
}
</unsigned></vector></algorithm></string></iostream>

Optimized Implementation with Character-by-Character Input

We can optimize by reading characters one by one and computing the hash on the fly, avoiding the need to store the entire string:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const unsigned long long BASE = 191; // Base for hash function

// Fast input function
unsigned long long fastRead() {
    unsigned long long num = 0;
    char c = getchar();
    while (c != '\n' && c != ' ' && c != EOF) {
        num = num * BASE + c;
        c = getchar();
    }
    return num;
}

int main() {
    int n;
    cin >> n;
    vector<unsigned long=""> hashes(n);
    
    for (int i = 0; i < n; i++) {
        unsigned long long currentHash = 0;
        char c = getchar();
        // Skip whitespace
        while (c == ' ' || c == '\n') {
            c = getchar();
        }
        // Process characters until whitespace or EOF
        while (c != ' ' && c != '\n' && c != EOF) {
            currentHash = currentHash * BASE + c;
            c = getchar();
        }
        hashes[i] = currentHash;
    }
    
    // Sort to group identical hashes together
    sort(hashes.begin(), hashes.end());
    
    // Count distinct hashes
    int distinctCount = 1;
    for (int i = 1; i < n; i++) {
        if (hashes[i] != hashes[i-1]) {
            distinctCount++;
        }
    }
    
    cout << distinctCount << endl;
    return 0;
}
</unsigned></vector></algorithm></iostream>

This implementation reads characters one by one, computes the hash value incrementally, and stores only the hash values rather than the full strings. This approach is more memory-efficient, especially for large inputs with many long strings.