String Algorithms

String Hashing

String hashing is a method to compare the equality of two strings in $O(1)$ rather than the naive $O(n)$ solution.

The hash is given by $\text{hash}(s)={\sum }_{i=0}^{n-1}s[i]\cdot p^i\mathrm{mod}m$ where $p$ and $m$ are some chosen positive numbers:

• If the input string $s$ is only lowercase, use $p=31$
• Else, if both uppercase and lowercase, use $p=53$
• Use $m=10^9+9$

Polynomial Hashing

We can implement String Hashing with Polynomial Hashing.

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

Hash of substrings

The greater power is when we want to compare substrings of a string. The following code counts the number of unique substrings.

int count_unique_substrings(string const& s) {
    int n = s.size();
 
    const int p = 31;
    const int m = 1e9 + 9;
    vector<long long> p_pow(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i-1] * p) % m;
 
    vector<long long> h(n + 1, 0);
    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
 
    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        set<long long> hs;
        for (int i = 0; i <= n - l; i++) {
            long long cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n-i-1]) % m;
            hs.insert(cur_h);
        }
        cnt += hs.size();
    }
    return cnt;
}
 

// Search for Duplicate Strings in an array of strings
vector<vector<int>> group_identical_strings(vector<string> const& s) {
    int n = s.size();
    vector<pair<long long, int>> hashes(n);
    for (int i = 0; i < n; i++)
        hashes[i] = {compute_hash(s[i]), i};
 
    sort(hashes.begin(), hashes.end());
 
    vector<vector<int>> groups;
    for (int i = 0; i < n; i++) {
        if (i == 0 || hashes[i].first != hashes[i-1].first)
            groups.emplace_back();
        groups.back().push_back(hashes[i].second);
    }
    return groups;
}