String Hashing

Definition

We define a function \(f\) that maps strings to integers, and this function \(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 to a range with a smaller value domain that is convenient for comparison.

Warning

The meaning of "smaller value domain" varies in different contexts.

In hash tables, the value domain needs to be small enough to accommodate linear space and time complexity.

In string hashing, the value domain needs to be small enough to allow fast comparison (e.g., \(10^9\) or \(10^{18}\) are acceptable for fast comparison).

At the same time, to reduce the hash collision rate, the value domain should not be too small.

Properties

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

When the hash function values are different, the two strings must be different.
When the hash function values are the same, the two strings are not necessarily the same (but they are likely to be the same, and we certainly hope they are always the same).

The phenomenon where the hash function values are the same but the original strings are different is called a hash collision.

Explanation

What should we focus on?

Time complexity and the accuracy of the hash.

Typically, we use the polynomial hash method. 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 function value is \(xb^2+yb+z\).

It is important to note that many people use another definition of the hash function: \(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 definitions of the hash function above are feasible. However, the formulas used to compute the hash value of substrings differ between the two. Therefore, be careful not to confuse these two different hashing methods.

Since the first hash definition is more convenient to compute, more widely used, and can be analogized to a \(b\)-ary number for easier understanding, the hash function discussed below in this article will be defined as \(f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M\).

Additionally, for convenience and to enlarge the modulus, in C++ we often use unsigned long long to define the result of the hash function. Due to the characteristics of C++, this effectively sets the modulus \(M\) to \(2^{64}\), which is also a good choice.

Accuracy will be discussed later.

Hash Error Rate Analysis

Hash Collisions

A hash collision occurs when two different strings map to the same hash value.

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

Then the probability of a hash collision is:

\[ p(n,d) = 1 - \frac{d!}{d^n\left(d-n\right)!} \approx 1 - \exp(-\frac{n(n-1)}{2d} ) \]

Proof

When each hash value is generated with equal probability, the probability of no hash collision is:

\[ \overline{p}(n,d) = 1 \cdot \left (1 - \frac{1}{d} \right) \cdot \left ( 1- \frac{2}{d}\right) \cdots \left ( 1- \frac{n-1}{d}\right) \]

Simplifying:

\[ \begin{aligned} \overline{p}(n,d) & = \frac{d}{d}\cdot \frac{d-1}{d}\cdot \frac{d-2}{d} \cdots \frac{d-n+1}{d}\\ & = \frac{d\cdot (d-1)\cdot (d-2)\cdots(d-n+1)}{d^n}\\ & = \frac{d!}{d^n\left(d-n\right)!} \end{aligned} \]

Thus, the probability of a hash collision is:

\[ p(n,d) = 1 - \frac{d!}{d^n\left(d-n\right)!} \]

This formula is still too complex; we simplify it further.

According to Taylor's formula:

\[ \exp(x) = \sum_{k=0}^{\infty}\frac{x^k}{k!}=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}+\cdots \]

When \(x\) is very small, \(\exp(x)\) approximates \(1+x\).

Substituting into the original formula for no hash collision:

\[ \overline{p}(n,d) \approx 1 \cdot \exp(-\frac{1}{d}) \cdot \exp(-\frac{2}{d}) \cdots \exp(-\frac{n-1}{d}) \]

Simplifying:

\[ \begin{aligned} \overline{p}(n,d) & \approx \exp(-\frac{1}{d} - \frac{2}{d} - \cdots -\frac{n-1}{d})\\ &=\exp(-\frac{n(n-1)}{2d} ) \end{aligned} \]

Thus, the probability of a hash collision is:

\[ p(n,d) \approx 1 - \exp(-\frac{n(n-1)}{2d}) \]

Breaking Large Modulus Hash

Consider the formula:

\[ p(n,d) \approx 1 - \exp(-\frac{n(n-1)}{2d} ) \]

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

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

For example:

If the character set is uppercase and lowercase letters and digits, and the modulus is \(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 their hash values are the same is as high as \(90\%\).

Breaking Natural Overflow Hash

Due to the large modulus of this hash, the above method cannot break it, so we need another approach.

First, this hash is of the form \(f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i}\). We discuss cases based on \(b\).

b is Even

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\), \(s_i\cdot b^l \equiv 0 \pmod M\).

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

aaa...a

baa...a

with length greater than \(64\) to cause a collision.

b is Odd

Define \(!s_i\) as reversing all characters in \(s_i\).

Example:

\(s_i = abaab\)

\(!s_i = babba\)

That is, change a to b and b to a.

Further, define \(hash_i\) as the hash value of \(s_i\), and \(!hash_i\) as the hash value of \(!s_i\).

Continuously construct \(s_i = s_{i-1} + !s_{i-1}\).

\(s_{12}\) and \(!s_{12}\) are the two strings we need.

Derivation

First, we have:

\[ \begin{aligned} hash_i = hash_{i-1}\cdot base^{2^{i-2}} + !hash_{i-1}\\ !hash_{i} = !hash_{i-1}\cdot base^{2^{i-2}}+hash_{i-1} \end{aligned} \]

Attempt to subtract:

\[ \begin{aligned} &hash_i - !hash_i\\ =\ &hash_{i-1}\cdot base^{2^{i-2}} + !hash_{i-1}-(!hash_{i-1}\cdot base^{2^{i-2}}+hash_{i-1})\\ =\ &(hash_{i-1}-!hash_{i-1})\cdot (base^{2^{i-2}}-1) \end{aligned} \]

We notice the appearance of \(2^i\), but the original expression is too complex. Attempt substitution:

Let:

\[ \begin{aligned} f_i = hash_i - !hash_i\\ g_i = base^{2^{i-2}}-1 \end{aligned} \]

According to the original expression:

\[ \begin{aligned} f_i &= f_{i-1} \cdot g_i\\ &=f_1 \cdot g_1 \cdot g_2 \cdots g_{i-1}\\ \end{aligned} \]

Since \(base^{2^{i-2}}\) is always odd, \(g_i\) is always even.

Thus:

\[ 2^{i-1} | f_i \]

But this is too large; we need \(i-1\ge 64\) to break it. Continue simplifying:

\[ g_i = base^{2^{i-2}}-1 = (base^{2^{i-3}}-1)\cdot(base^{2^{i-3}}+1)\\ \]

That is, \(g_i\) is of the form \(g_{i-1} \cdot c\ (c \equiv 0 \pmod 2)\).

So \(2 | s_1\), \(4 | s_2\), ..., i.e.,

\[ \begin{aligned} & 2^i &| g_i\\ &2^1\cdot2^2\cdot2^3\cdots2^{i-1} &| f_i\\ &2^{i(i-1)/2} &| f_i \end{aligned} \]

Thus, when \(i=12\), we can achieve \(2^{64} | hash_i - !hash_i\), meeting the requirement.

Example Problems

Example: BZOJ 3097 Hash Killer I

Given a hash implemented with natural overflow, construct a string to break it.

Example: BZOJ 3097 Hash Killer II

Given a hash implemented with a large modulus, construct a string to break it.

Example: Luogu U461211 String Hash (Enhanced Data)

Given \(n\) strings, determine how many distinct strings there are.

Improvements to Hashing

Multi-Value Hash

After seeing so many methods to break hashes, there are naturally solutions.

Multi-value hash involves using multiple hash functions, each with a different modulus, to solve the hash collision problem.

When comparing, if any of the hash values differ, the two strings are considered different. If all hash values are the same, the two strings are considered the same.

Generally, a double-value hash is sufficient.

Multiple Queries for Substring Hash

Computing the hash value of a string once has a complexity of \(O(n)\), where \(n\) is the string length, which is no different from brute-force matching. If we need to query the hash value of substrings multiple times, recomputing each time is highly inefficient.

A common approach is to preprocess the hash value for each prefix of the entire string, treating the hash value as a \(b\)-ary number modulo \(M\). This allows us to quickly compute the hash of any substring:

Let \(f_i(s)\) denote \(f(s[1..i])\), i.e., the hash value of the prefix of length \(i\) of the original string. 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 quickly compute \(f(s[l..r])\) in a manner similar to prefix sums. By definition, the hash value of substring \(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, we find that \(f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}\) holds (you can manually verify this). Thus, we can use this formula to quickly obtain the hash value of a substring. Here, \(b^{r-l+1}\) can be preprocessed in \(O(n)\) and answered in \(O(1)\) per query (or answered in \(O(\log n)\) per query using fast exponentiation).

Implementation

Modulus Hash:

Note: Low efficiency, not recommended in practice.

C++Python

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

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-Value Hash:

C++Python

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

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 computing the hash value of the pattern string, compute the hash value of each substring of the text string with the same length as the pattern string, and compare them with the pattern string's hash value.

String Matching Allowing \(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 string. \(s'\) matches \(s\) if and only if \(s'\) has the same length as \(s\) and at most \(k\) positions have different characters. Here, \(1\leq n,m\leq 10^6\), \(0\leq k\leq 5\).

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

Enumerate all possible matching substrings. Suppose the current substring is \(s'\). Use hashing + binary search to quickly find the first position where \(s'\) and \(p\) differ. Then, remove the mismatched part and the preceding part from \(s'\) and \(p\), and continue searching for the next mismatch. This process occurs at most \(k\) times.

Total time complexity is \(O(m+kn\log_2m)\).

Longest Palindromic Substring

Binary search the answer. When checking feasibility, enumerate the palindrome center (axis of symmetry) and use hashing to check if both sides are equal. Preprocess both forward and backward hash values. Time complexity is \(O(n\log n)\).

This problem can also be solved in \(O(n)\) time using Manacher's algorithm.

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

Longest Common Substring

Problem: Given \(m\) non-empty strings with a total length not exceeding \(n\), find the longest common substring among 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. Thus, we can binary search the length of the longest common substring. Suppose the current length is \(k\). The logic of check(k) is: hash all substrings of length \(k\) of each string and store the hash values in \(n\) hash tables. Then compute the intersection.

Time complexity is \(O(m+n\log n)\).

Counting 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, we iterate over all substring lengths \(l=1,\cdots ,n\). For each length \(l\), we compute the hash value of each substring, multiply it 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 length \(l\), and this number is added to the final answer.

For convenience, we use \(h [i]\) as the hash of the prefix up to \(i\), and define \(h[0]=0\).

Reference Code

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

CF1200E Compress Words

You are given several strings. Initially, the answer string is empty. In the \(i\)-th step, append the \(i\)-th string to the answer string, but remove the longest possible overlapping part (i.e., remove the longest string that is both a suffix of the current answer string and a prefix of the \(i\)-th string). Find the final string.

The number of strings does not exceed \(10^5\), and the total length does not exceed \(10^6\).

Solution

Each time, we need to find the longest string that is both a suffix of the current answer string and a prefix of the \(i\)-th string. Enumerate the length of this string and compare using hashing.

Of course, this problem can also be solved using the KMP algorithm.

Reference Code

#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 character count and each character
    for (int i = 0; i < HASH_CNT; ++i) {  // Preprocessing for double hashing
      pwMod[i][ls] =
          1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // Get b^ls
      hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
    }
  }

  vector<int> getHash(int l, int r) {  // Get 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 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 answer array
}

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

Parts of this page are translated from the blog post строковый хеш 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.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用