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;
}

USACO Implementation

A template from here https://usaco.guide/gold/hashing?lang=cpp

• Thanks to this video for the shoutout https://www.youtube.com/watch?v=-j2W7pub49U

Try using it for this problem https://codeforces.com/contest/1944/problem/D

class HashedString {
  private:
	// change M and B if you want
	static const long long M = 1e9 + 9;
	static const long long B = 9973;
 
	// pow[i] contains B^i % M
	static vector<long long> pow;
 
	// p_hash[i] is the hash of the first i characters of the given string
	vector<long long> p_hash;
 
  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
 
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
		}
	}
 
	long long get_hash(int start, int end) {
		long long raw_val =
		    (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
		return (raw_val % M + M) % M;
	}
};
vector<long long> HashedString::pow = {1};