String hashing

Definition

We define a function $f$ that maps strings to integers; this $f$ is called a hash function.

We hope that this function $f$ can conveniently help us determine whether two strings are equal.

The idea of hashing

The core idea of hashing is to map the input into a relatively small range whose values are convenient to compare.

Properties

More specifically, the most important properties of a hash function can be summarized as follows:

1. If the hash values are different, the two strings must be different;

2. If the hash values are the same, the two strings are not necessarily the same (although they are likely to be the same, and of course we would like them to always be the same).

   We call the phenomenon in which two different original strings have the same hash value a hash collision.

Explanation

What do we need to pay attention to?

Time complexity and hash accuracy.

We usually use polynomial hashing. For a string $s$ of length $l$, we can define the polynomial hash function as $f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$. For example, for the string $xyz$, its hash value is $xb^2+yb+z$.

It is worth noting that many people also use another definition of the hash function, namely $f(s) = \sum_{i=1}^{l} s[i] \times b^{i-1} \pmod M$. Under this definition, the hash value of the same string $xyz$ becomes $x+yb+zb^2$.

Clearly, both of the above hash-function definitions are valid, but the formulas used to calculate substring hash values later are different for the two definitions. Therefore, be very careful not to confuse these two different hashing methods.

Because the first hash definition is easier to calculate, is more widely used, and can be understood by analogy with a base-$b$ number, all hash functions discussed below in this article use $f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$ as their definition.

Also, for convenience and to use a larger modulus, in C++ we sometimes use unsigned long long to define the result of the hash function. Due to C++'s behavior, this is equivalent to setting the modulus $M$ to $2^{64}$, which is also a good choice.

Accuracy will be discussed later.

Hash collision probability analysis

Hash collisions

A hash collision means that two different strings map to the same hash value.

Let the hash value space (the number of all possible strings) be $d$, and let the number of computations (the number of strings to be hashed) be $n$.

Then the probability of a hash collision is:

Breaking large-modulus hashes

Observe the formula:

To break a hash, we need to satisfy the following conditions:

1. $d$ should be greater than the modulus.
2. $1-p(d,n)$ should be as small as possible.

For example:

If the character set consists of uppercase and lowercase letters and digits, with modulus $10^9+7$:

$\log_{62}10^9+7\approx 6$

$p(10^6,62^{6}) \approx 0.9$

Thus, for this range, if we randomly generate $10^6$ strings of length $6$, the probability that they have the same hash value is as high as $90\%$.

Breaking natural-overflow hashes

This hash has a modulus that is too large to be broken by the method above, so we need another method.

First, this hash has the form $f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i}$, so we discuss cases according to $b$.

Even b

Here $f(s) = s_1\cdot b^l + s_2\cdot b^{l-1} + \cdots + s_l\cdot b \pmod M$, where $M$ is $2^{64}$.

It is easy to see that if $l \ge 64$, then $s_i\cdot b^l \equiv 0 \pmod M$.

Therefore, we only need to construct strings of the form:

aaa...a

baa...a

with length greater than $64$ to obtain a collision.

Odd b

Define $!s_i$ as the string obtained by flipping every character in $s_i$.

Example:

$s_i = abaab$

$!s_i = babba$

That is, turn a into b, and turn b into a.

Now define $hash_i$ as the hash value of $s_i$, and $!hash_i$ as the hash value of $!s_i$.

Repeatedly construct $s_i = s_{i-1} + !s_{i-1}$.

$s_{12}$ and $!s_{12}$ are the two strings we need.

Example problems

Improving Hashing

Multiple-value hashing

After seeing so many ways to break hashes above, there are of course ways to solve the problem as well.

Multiple-value hashing uses multiple hash functions, each with a different modulus, which solves the hash-collision problem.

When comparing, if even one of the hash values differs, regard the two strings as different; if all hash values are the same, regard the two strings as the same.

In general, double hashing is sufficient.

Hashing substrings for multiple queries

Computing the hash of one string once has complexity $O(n)$, where $n$ is the string length, so it is no different from brute-force matching. If we need to query substring hashes of one string many times, recomputing each time is very inefficient.

The usual method is to precompute the hash value of every prefix of the entire string. Regard the hash value as the result of taking a base-$b$ number modulo $M$, so that each substring hash can then be found quickly:

Let $f_i(s)$ denote $f(s[1..i])$, namely the hash value of the prefix of the original string of length $i$. By definition, $f_i(s)=s[1]\cdot b^{i-1}+s[2]\cdot b^{i-2}+\dots+s[i-1]\cdot b+s[i]$

Now we want to find $f(s[l..r])$ quickly in a way similar to prefix sums. By definition, the hash value of the string $s[l..r]$ is $f(s[l..r])=s[l]\cdot b^{r-l}+s[l+1]\cdot b^{r-l-1}+\dots+s[r-1]\cdot b+s[r]$

Comparing the two expressions above, we find that $f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}$ holds (you can substitute manually to verify it), so this expression gives the substring hash quickly. The value $b^{r-l+1}$ can be precomputed in $O(n)$ and then each query can be answered in $O(1)$ (or each query can be answered with fast exponentiation in $O(\log n)$).

Implementation

Modular hash

Note: it is less efficient and not recommended in practice.

C++

using std::string;

constexpr int M = 1e9 + 7;
constexpr int B = 233;

using ll = long long;

int get_hash(const string& s) {
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    res = ((ll)res * B + s[i]) % M;
  }
  return res;
}

bool cmp(const string& s, const string& t) {
  return get_hash(s) == get_hash(t);
}

Python

M = int(1e9 + 7)
B = 233

def get_hash(s):
    res = 0
    for char in s:
        res = (res * B + ord(char)) % M
    return res

def cmp(s, t):
    return get_hash(s) == get_hash(t)

Double hash

C++

using ull = unsigned long long;
ull base = 131;
ull mod1 = 212370440130137957, mod2 = 1e9 + 7;

ull get_hash1(std::string s) {
  int len = s.size();
  ull ans = 0;
  for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod1;
  return ans;
}

ull get_hash2(std::string s) {
  int len = s.size();
  ull ans = 0;
  for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod2;
  return ans;
}

bool cmp(const std::string s, const std::string t) {
  bool f1 = get_hash1(s) != get_hash1(t);
  bool f2 = get_hash2(s) != get_hash2(t);
  return f1 || f2;
}

Python

def get_hash1(s: str) -> int:
    base = 131
    mod1 = 212370440130137957
    ans = 0
    for char in s:
        ans = (ans * base + ord(char)) % mod1
    return ans

def get_hash2(s: str) -> int:
    base = 131
    mod2 = 1000000007
    ans = 0
    for char in s:
        ans = (ans * base + ord(char)) % mod2
    return ans

def cmp(s: str, t: str) -> bool:
    f1 = get_hash1(s) != get_hash1(t)
    f2 = get_hash2(s) != get_hash2(t)
    return f1 or f2

Applications of Hashing

String matching

After calculating the hash value of the pattern, calculate the hash values of every substring of the text whose length equals the pattern length, and compare each with the pattern's hash value.

String matching with up to $k$ mismatches

Problem: Given a source string $s$ of length $n$ and a pattern string $p$ of length $m$, find how many substrings of the source string match the pattern. $s'$ matches $s$ if and only if $s'$ and $s$ have the same length and differ at no more than $k$ positions. Here $1\leq n,m\leq 10^6$ and $0\leq k\leq 5$.

This problem cannot be solved with KMP, but it can be solved with hashing plus binary search.

Enumerate all possible matching substrings. Suppose the currently enumerated substring is $s'$. Hashing plus binary search can quickly find the first position at which $s'$ and $p$ differ. Then delete from $s'$ and $p$ the mismatching position and all positions before it, and continue searching for the next mismatch. This process occurs at most $k$ times.

The total time complexity is $O(m+kn\log_2m)$.

Longest palindromic substring

Binary-search the answer. When checking feasibility, enumerate the palindrome centers (axes of symmetry) and use hashes to determine whether the two sides are equal. The hashes in forward and reverse order need to be precomputed separately. The time complexity is $O(n\log n)$.

This problem can be solved by the Manacher algorithm in $O(n)$ time.

Hashing can also solve this problem in $O(n)$. Specifically, let $R_i$ denote the length of the longest palindrome ending at $i$; then the answer is $\max_{i=1}^nR_i$. Since $R_i\leq R_{i-1}+2$, we only need to brute-force downward from $R_{i-1}+2$ until we find the first palindrome. Let $z$ denote the current enumerated $R_i$, initially $0$. Whenever $i$ increases, $z$ increases by $2$, and each brute-force loop then decreases it by $1$. Thus, the brute-force loop occurs at most $2n$ times, and the total time complexity is $O(n)$.

Longest common substring

Problem: Given $m$ nonempty strings with total length at most $n$, find the longest common substring of all strings; if there are multiple, output any one. Here $1\leq m, n\leq 10^6$.

Clearly, if a longest common substring of length $k$ exists, then a common substring of length $k-1$ must also exist. Therefore, we can binary-search the length of the longest common substring. Suppose the current length is $k$. The logic of check(k) is to hash all substrings of length $k$ in every string and store the hash values in $n$ hash tables. Then take their intersection.

The time complexity is $O(m+n\log n)$.

Determining the number of distinct substrings in a string

Problem: Given a string of length $n$ consisting only of lowercase English letters, find the number of distinct substrings in the string.

To solve this problem, we enumerate all substrings of each length $l=1,\cdots ,n$. For each length $l$, we multiply its hash value by the same power of $b$ and store it in an array. The number of distinct elements in the array equals the number of distinct substrings of that length, and this number is added to the final answer.

For convenience, we use $h [i]$ as the prefix characters of the hash and define $h[0]=0$.

int count_unique_substrings(string const& s) {
  int n = s.size();

  constexpr static int b = 31;
  constexpr static int m = 1e9 + 9;
  vector<long long> b_pow(n);
  b_pow[0] = 1;
  for (int i = 1; i < n; i++) b_pow[i] = (b_pow[i - 1] * b) % m;

  vector<long long> h(n + 1, 0);
  for (int i = 0; i < n; i++)
    h[i + 1] = (h[i] + (s[i] - 'a' + 1) * b_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 * b_pow[n - i - 1]) % m;
      hs.insert(cur_h);
    }
    cnt += hs.size();
  }
  return cnt;
}

Example problems

#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

constexpr int L = 1e6 + 5;
constexpr int HASH_CNT = 2;

int hashBase[HASH_CNT] = {29, 31};
int hashMod[HASH_CNT] = {int(1e9 + 9), 998244353};

struct StringWithHash {
  char s[L];
  int ls;
  int hsh[HASH_CNT][L];
  int pwMod[HASH_CNT][L];

  void init() {  // Initialize
    ls = 0;
    for (int i = 0; i < HASH_CNT; ++i) {
      hsh[i][0] = 0;
      pwMod[i][0] = 1;
    }
  }

  StringWithHash() { init(); }

  void extend(char c) {
    s[++ls] = c;                          // Record the character count and each character
    for (int i = 0; i < HASH_CNT; ++i) {  // Precompute the double hash
      pwMod[i][ls] =
          1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // Obtain b^ls
      hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
    }
  }

  vector<int> getHash(int l, int r) {  // Obtain the hash value
    vector<int> res(HASH_CNT, 0);
    for (int i = 0; i < HASH_CNT; ++i) {
      int t =
          (hsh[i][r] - 1ll * hsh[i][l - 1] * pwMod[i][r - l + 1]) % hashMod[i];
      t = (t + hashMod[i]) % hashMod[i];
      res[i] = t;
    }
    return res;
  }
};

bool equal(const vector<int> &h1, const vector<int> &h2) {
  assert(h1.size() == h2.size());
  for (unsigned i = 0; i < h1.size(); i++)
    if (h1[i] != h2[i]) return false;
  return true;
}

int n;
StringWithHash s, t;
char str[L];

void work() {
  int len = strlen(str);  // Get the string length
  t.init();
  for (int j = 0; j < len; ++j) t.extend(str[j]);
  int d = 0;
  for (int j = min(len, s.ls); j >= 1; --j) {
    if (equal(t.getHash(1, j), s.getHash(s.ls - j + 1, s.ls))) {  // Compare hash values
      d = j;
      break;
    }
  }
  for (int j = d; j < len; ++j) s.extend(str[j]);  // Update the answer string
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> str;
    work();
  }
  cout << s.s + 1 << '\n';
  return 0;
}

This page is partially translated from the blog String hash and its English translation String Hashing. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.