跳转至

字符串哈希

定義

我們定義一個把字符串映射到整數的函數 \(f\)，這個 \(f\) 稱為是 Hash 函數。

我們希望這個函數 \(f\) 可以方便地幫我們判斷兩個字符串是否相等。

Hash 的思想

Hash 的核心思想在於，將輸入映射到一個值域較小、可以方便比較的範圍。

Warning

這裏的「值域較小」在不同情況下意義不同。

在 哈希表 中，值域需要小到能夠接受線性的空間與時間複雜度。

在字符串哈希中，值域需要小到能夠快速比較（\(10^9\)、\(10^{18}\) 都是可以快速比較的）。

同時，為了降低哈希衝突率，值域也不能太小。

性質

具體來説，哈希函數最重要的性質可以概括為下面兩條：

  1. 在 Hash 函數值不一樣的時候，兩個字符串一定不一樣；

  2. 在 Hash 函數值一樣的時候，兩個字符串不一定一樣（但有大概率一樣，且我們當然希望它們總是一樣的）。

    我們將 Hash 函數值一樣但原字符串不一樣的現象稱為哈希碰撞。

解釋

我們需要關注的是什麼？

時間複雜度和 Hash 的準確率。

通常我們採用的是多項式 Hash 的方法，對於一個長度為 \(l\) 的字符串 \(s\) 來説，我們可以這樣定義多項式 Hash 函數：\(f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M\)。例如，對於字符串 \(xyz\)，其哈希函數值為 \(xb^2+yb+z\)。

特別要説明的是，也有很多人使用的是另一種 Hash 函數的定義，即 \(f(s) = \sum_{i=1}^{l} s[i] \times b^{i-1} \pmod M\)，這種定義下，同樣的字符串 \(xyz\) 的哈希值就變為了 \(x+yb+zb^2\) 了。

顯然，上面這兩種哈希函數的定義函數都是可行的，但二者在之後會講到的計算子串哈希值時所用的計算式是不同的，因此千萬注意 不要弄混了這兩種不同的 Hash 方式。

由於前者的 Hash 定義計算更簡便、使用人數更多、且可以類比為一個 \(b\) 進制數來幫助理解，所以本文下面所將要討論的都是使用 \(f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M\) 來定義的 Hash 函數。

下面講一下如何選擇 \(M\) 和計算哈希碰撞的概率。

這裏 \(M\) 需要選擇一個素數（至少要比最大的字符要大），\(b\) 可以任意選擇。

如果我們用未知數 \(x\) 替代 \(b\)，那麼 \(f(s)\) 實際上是多項式環 \(\mathbb{Z}_M[x]\) 上的一個多項式。考慮兩個不同的字符串 \(s,t\)，有 \(f(s)=f(t)\)。我們記 \(h(x)=f(s)-f(t)=\sum_{i=1}^l(s[i]-t[i])x^{l-i}\pmod M\)，其中 \(l=\max(|s|,|t|)\)。可以發現 \(h(x)\) 是一個 \(l-1\) 階的非零多項式。

如果 \(s\) 與 \(t\) 在 \(x=b\) 的情況下哈希碰撞，則 \(b\) 是 \(h(x)\) 的一個根。由於 \(h(x)\) 在 \(\mathbb{Z}_M\) 是一個域（等價於 \(M\) 是一個素數，這也是為什麼 \(M\) 要選擇素數的原因）的時候，最多有 \(l-1\) 個根，如果我們保證 \(b\) 是從 \([0,M)\) 之間均勻隨機選取的，那麼 \(f(s)\) 與 \(f(t)\) 碰撞的概率可以估計為 \(\frac{l-1}{M}\)。簡單驗算一下，可以發現如果兩個字符串長度都是 \(1\) 的時候，哈希碰撞的概率為 \(\frac{1-1}{M}=0\)，此時不可能發生碰撞。

實現

參考代碼：（效率低下的版本，實際使用時一般不會這麼寫）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
using std::string;

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

typedef long long ll;

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)

Hash 的分析與改進

錯誤率

假定哈希函數將字符串隨機地映射到大小為 \(M\) 的值域中，總共有 \(n\) 個不同的字符串，那麼未出現碰撞的概率是 \(\prod_{i = 0}^{n-1} \frac{M-i}{M}\)（第 \(i\) 次進行哈希時，有 \(\frac{M-i}{M}\) 的概率不會發生碰撞）。在隨機數據下，若 \(M=10^9 + 7\)，\(n=10^6\)，未出現碰撞的概率是極低的。

所以，進行字符串哈希時，經常會對兩個大質數分別取模，這樣的話哈希函數的值域就能擴大到兩者之積，錯誤率就非常小了。

多次詢問子串哈希

單次計算一個字符串的哈希值複雜度是 \(O(n)\)，其中 \(n\) 為串長，與暴力匹配沒有區別，如果需要多次詢問一個字符串的子串的哈希值，每次重新計算效率非常低下。

一般採取的方法是對整個字符串先預處理出每個前綴的哈希值，將哈希值看成一個 \(b\) 進制的數對 \(M\) 取模的結果，這樣的話每次就能快速求出子串的哈希了：

令 \(f_i(s)\) 表示 \(f(s[1..i])\)，即原串長度為 \(i\) 的前綴的哈希值，那麼按照定義有 \(f_i(s)=s[1]\cdot b^{i-1}+s[2]\cdot b^{i-2}+\dots+s[i-1]\cdot b+s[i]\)

現在，我們想要用類似前綴和的方式快速求出 \(f(s[l..r])\)，按照定義有字符串 \(s[l..r]\) 的哈希值為 \(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]\)

對比觀察上述兩個式子，我們發現 \(f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}\) 成立（可以手動代入驗證一下），因此我們用這個式子就可以快速得到子串的哈希值。其中 \(b^{r-l+1}\) 可以 \(O(n)\) 的預處理出來然後 \(O(1)\) 的回答每次詢問（當然也可以快速冪 \(O(\log n)\) 的回答每次詢問）。

Hash 的應用

字符串匹配

求出模式串的哈希值後，求出文本串每個長度為模式串長度的子串的哈希值，分別與模式串的哈希值比較即可。

允許 \(k\) 次失配的字符串匹配

問題：給定長為 \(n\) 的源串 \(s\)，以及長度為 \(m\) 的模式串 \(p\)，要求查找源串中有多少子串與模式串匹配。\(s'\) 與 \(s\) 匹配，當且僅當 \(s'\) 與 \(s\) 長度相同，且最多有 \(k\) 個位置字符不同。其中 \(1\leq n,m\leq 10^6\)，\(0\leq k\leq 5\)。

這道題無法使用 KMP 解決，但是可以通過哈希 + 二分來解決。

枚舉所有可能匹配的子串，假設現在枚舉的子串為 \(s'\)，通過哈希 + 二分可以快速找到 \(s'\) 與 \(p\) 第一個不同的位置。之後將 \(s'\) 與 \(p\) 在這個失配位置及之前的部分刪除掉，繼續查找下一個失配位置。這樣的過程最多發生 \(k\) 次。

總的時間複雜度為 \(O(m+kn\log_2m)\)。

最長迴文子串

二分答案，判斷是否可行時枚舉迴文中心（對稱軸），哈希判斷兩側是否相等。需要分別預處理正着和倒着的哈希值。時間複雜度 \(O(n\log n)\)。

這個問題可以使用 manacher 算法 在 \(O(n)\) 的時間內解決。

通過哈希同樣可以 \(O(n)\) 解決這個問題，具體方法就是記 \(R_i\) 表示以 \(i\) 作為結尾的最長迴文的長度，那麼答案就是 \(\max_{i=1}^nR_i\)。考慮到 \(R_i\leq R_{i-1}+2\)，因此我們只需要暴力從 \(R_{i-1}+2\) 開始遞減，直到找到第一個迴文即可。記變量 \(z\) 表示當前枚舉的 \(R_i\)，初始時為 \(0\)，則 \(z\) 在每次 \(i\) 增大的時候都會增大 \(2\)，之後每次暴力循環都會減少 \(1\)，故暴力循環最多發生 \(2n\) 次，總的時間複雜度為 \(O(n)\)。

最長公共子字符串

問題：給定 \(m\) 個總長不超過 \(n\) 的非空字符串，查找所有字符串的最長公共子字符串，如果有多個，任意輸出其中一個。其中 \(1\leq m, n\leq 10^6\)。

很顯然如果存在長度為 \(k\) 的最長公共子字符串，那麼 \(k-1\) 的公共子字符串也必定存在。因此我們可以二分最長公共子字符串的長度。假設現在的長度為 \(k\)，check(k) 的邏輯為我們將所有所有字符串的長度為 \(k\) 的子串分別進行哈希，將哈希值放入 \(n\) 個哈希表中存儲。之後求交集即可。

時間複雜度為 \(O(m+n\log n)\)。

確定字符串中不同子字符串的數量

問題：給定長為 \(n\) 的字符串，僅由小寫英文字母組成，查找該字符串中不同子串的數量。

為了解決這個問題，我們遍歷了所有長度為 \(l=1,\cdots ,n\) 的子串。對於每個長度為 \(l\)，我們將其 Hash 值乘以相同的 \(b\) 的冪次方，並存入一個數組中。數組中不同元素的數量等於字符串中長度不同的子串的數量，並此數字將添加到最終答案中。

為了方便起見，我們將使用 \(h [i]\) 作為 Hash 的前綴字符，並定義 \(h[0]=0\)。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int count_unique_substrings(string const& s) {
  int n = s.size();

  const int b = 31;
  const 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;
}

例題

CF1200E Compress Words

給你若干個字符串，答案串初始為空。第 \(i\) 步將第 \(i\) 個字符串加到答案串的後面，但是儘量地去掉重複部分（即去掉一個最長的、是原答案串的後綴、也是第 \(i\) 個串的前綴的字符串），求最後得到的字符串。

字符串個數不超過 \(10^5\)，總長不超過 \(10^6\)。

題解

每次需要求最長的、是原答案串的後綴、也是第 \(i\) 個串的前綴的字符串。枚舉這個串的長度，哈希比較即可。

當然，這道題也可以使用 KMP 算法 解決。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

const int L = 1e6 + 5;
const 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() {  // 初始化
    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;                          // 记录字符数和每一个字符
    for (int i = 0; i < HASH_CNT; ++i) {  // 双哈希的预处理
      pwMod[i][ls] =
          1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // 得到b^ls
      hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
    }
  }

  vector<int> getHash(int l, int r) {  // 得到哈希值
    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);  // 取字符串长度
  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))) {  // 比较哈希值
      d = j;
      break;
    }
  }
  for (int j = d; j < len; ++j) s.extend(str[j]);  // 更新答案数组
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", str);
    work();
  }
  printf("%s\n", s.s + 1);
  return 0;
}

本頁面部分內容譯自博文 строковый хеш 與其英文翻譯版 String Hashing。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

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