跳转至

# 字符串哈希

## 定义

我们定义一个把字符串映射到整数的函数 𝑓 f，这个 𝑓 f 称为是 Hash 函数．

我们希望这个函数 𝑓 f 可以方便地帮我们判断两个字符串是否相等．

## Hash 的思想

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围．

Warning

这里的「值域较小」在不同情况下意义不同．

在 哈希表 中，值域需要小到能够接受线性的空间与时间复杂度．

在字符串哈希中，值域需要小到能够快速比较（1 0 9 10 9、1 0 1 8 10 18 都是可以快速比较的）．

同时，为了降低哈希冲突率，值域也不能太小．

## 性质

具体来说，哈希函数最重要的性质可以概括为下面两条：

1. 在 Hash 函数值不一样的时候，两个字符串一定不一样；

2. 在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）．

   我们将 Hash 函数值一样但原字符串不一样的现象称为哈希碰撞．

## 解释

我们需要关注的是什么？

时间复杂度和 Hash 的准确率．

通常我们采用的是多项式 Hash 的方法，对于一个长度为 𝑙 l 的字符串 𝑠 s 来说，我们可以这样定义多项式 Hash 函数：𝑓(𝑠) =∑𝑙 𝑖=1 𝑠[𝑖] ×𝑏 𝑙−𝑖(m o d 𝑀)f(s)=∑i=1 l s[i]×b l−i(mod M)．例如，对于字符串 𝑥 𝑦 𝑧 x y z，其哈希函数值为 𝑥 𝑏 2 +𝑦 𝑏 +𝑧 x b 2+y b+z．

特别要说明的是，也有很多人使用的是另一种 Hash 函数的定义，即 𝑓(𝑠) =∑𝑙 𝑖=1 𝑠[𝑖] ×𝑏 𝑖−1(m o d 𝑀)f(s)=∑i=1 l s[i]×b i−1(mod M)，这种定义下，同样的字符串 𝑥 𝑦 𝑧 x y z 的哈希值就变为了 𝑥 +𝑦 𝑏 +𝑧 𝑏 2 x+y b+z b 2 了．

显然，上面这两种哈希函数的定义函数都是可行的，但二者在之后会讲到的计算子串哈希值时所用的计算式是不同的，因此千万注意 不要弄混了这两种不同的 Hash 方式．

由于前者的 Hash 定义计算更简便、使用人数更多、且可以类比为一个 𝑏 b 进制数来帮助理解，所以本文下面所将要讨论的都是使用 𝑓(𝑠) =∑𝑙 𝑖=1 𝑠[𝑖] ×𝑏 𝑙−𝑖(m o d 𝑀)f(s)=∑i=1 l s[i]×b l−i(mod M) 来定义的 Hash 函数．

还有，有时为了方便和扩大模数，我们在 C++ 中我们会使用 `unsigned long long` 来定义 Hash 函数的结果．由于 C++ 的特性，我们相当于把模数 𝑀 M 定为 2 6 4 2 64，也是一个不错的选择．

准确率会在后面讨论．

## Hash 的错误率分析

### Hash 冲突

Hash 冲突是指两个不同的字符串映射到相同的 Hash 值．

我们设 Hash 的取值空间（所有可能出现的字符串的数量）为 𝑑 d，计算次数（要计算的字符串数量）为 𝑛 n．

则 Hash 冲突的概率为：

𝑝(𝑛,𝑑)=1−𝑑!𝑑 𝑛(𝑑−𝑛)!≈1−e x p⁡(−𝑛(𝑛−1)2 𝑑)p(n,d)=1−d!d n(d−n)!≈1−exp⁡(−n(n−1)2 d)
证明

当 Hash 中每个值生成概率相同时，Hash 不冲突的概率为：

――𝑝(𝑛,𝑑)=1⋅(1−1 𝑑)⋅(1−2 𝑑)⋯(1−𝑛−1 𝑑)p―(n,d)=1⋅(1−1 d)⋅(1−2 d)⋯(1−n−1 d)

化简得到：

――𝑝(𝑛,𝑑)=𝑑 𝑑⋅𝑑−1 𝑑⋅𝑑−2 𝑑⋯𝑑−𝑛+1 𝑑=𝑑⋅(𝑑−1)⋅(𝑑−2)⋯(𝑑−𝑛+1)𝑑 𝑛=𝑑!𝑑 𝑛(𝑑−𝑛)!p―(n,d)=d d⋅d−1 d⋅d−2 d⋯d−n+1 d=d⋅(d−1)⋅(d−2)⋯(d−n+1)d n=d!d n(d−n)!

则 Hash 冲突的概率为：

𝑝(𝑛,𝑑)=1−𝑑!𝑑 𝑛(𝑑−𝑛)!p(n,d)=1−d!d n(d−n)!

这个公式还是太复杂了，我们进一步化简．

根据泰勒公式：

e x p⁡(𝑥)=∞∑𝑘=0 𝑥 𝑘 𝑘!=1+𝑥+𝑥 2 2+𝑥 3 6+𝑥 4 2 4+⋯exp⁡(x)=∑k=0∞x k k!=1+x+x 2 2+x 3 6+x 4 24+⋯

当 𝑥 x 为一个极小值时，e x p⁡(𝑥)exp⁡(x) 趋近于 1 +𝑥 1+x．

将它带入 Hash 不冲突的原始公式：

――𝑝(𝑛,𝑑)≈1⋅e x p⁡(−1 𝑑)⋅e x p⁡(−2 𝑑)⋯e x p⁡(−𝑛−1 𝑑)p―(n,d)≈1⋅exp⁡(−1 d)⋅exp⁡(−2 d)⋯exp⁡(−n−1 d)

化简：

――𝑝(𝑛,𝑑)≈e x p⁡(−1 𝑑−2 𝑑−⋯−𝑛−1 𝑑)=e x p⁡(−𝑛(𝑛−1)2 𝑑)p―(n,d)≈exp⁡(−1 d−2 d−⋯−n−1 d)=exp⁡(−n(n−1)2 d)

则 Hash 冲突的概率为：

𝑝(𝑛,𝑑)≈1−e x p⁡(−𝑛(𝑛−1)2 𝑑)p(n,d)≈1−exp⁡(−n(n−1)2 d)

### 卡大模数 Hash

注意到这个公式：

𝑝(𝑛,𝑑)≈1−e x p⁡(−𝑛(𝑛−1)2 𝑑)p(n,d)≈1−exp⁡(−n(n−1)2 d)

为了卡掉 Hash，我们要满足以下条件：

1. 𝑑 d 要大于模数．
2. 1 −𝑝(𝑑,𝑛)1−p(d,n) 要尽量小．

举个例子：

若字符集为 大小写字母和数字，模数为 1 0 9 +7 10 9+7 时：

l o g 6 2⁡1 0 9 +7 ≈6 log 62⁡10 9+7≈6

𝑝(1 0 6,6 2 6) ≈0.9 p(10 6,62 6)≈0.9

所以对于这个范围，我们随机生成 1 0 6 10 6 个长度为 6 6 的字符串，它们 Hash 值相同的概率高达 9 0%90%．

### 卡自然溢出 Hash

这种 Hash 由于模数太大，用上面的方法卡不了，所以我们需要另一种方法．

首先，这种 Hash 是形如 𝑓(𝑠) =∑𝑙 𝑖=1 𝑠[𝑖] ×𝑏 𝑙−𝑖 f(s)=∑i=1 l s[i]×b l−i，我们根据 𝑏 b 来分类讨论．

#### b 为偶数

此时 𝑓(𝑠) =𝑠 1 ⋅𝑏 𝑙 +𝑠 2 ⋅𝑏 𝑙−1 +⋯ +𝑠 𝑙 ⋅𝑏(m o d 𝑀)f(s)=s 1⋅b l+s 2⋅b l−1+⋯+s l⋅b(mod M)，其中 𝑀 M 为 2 6 4 2 64．

容易发现若 𝑙 ≥6 4 l≥64，𝑠 𝑖 ⋅𝑏 𝑙 ≡0(m o d 𝑀)s i⋅b l≡0(mod M)．

所以我们只要构造形如：

`aaa...a`

`baa...a`

且长度大于 6 4 64 的字符串就能冲突．

#### b 为奇数

定义 !𝑠 𝑖!s i 为把 𝑠 𝑖 s i 中所有字符反转．

例：

𝑠 𝑖 =𝑎 𝑏 𝑎 𝑎 𝑏 s i=a b a a b

!𝑠 𝑖 =𝑏 𝑎 𝑏 𝑏 𝑎!s i=b a b b a

即把 `a` 变成 `b`，把 `b` 变成 `a`．

再定义 ℎ 𝑎 𝑠 ℎ 𝑖 h a s h i 为 𝑠 𝑖 s i 的 Hash 值，!ℎ 𝑎 𝑠 ℎ 𝑖!h a s h i 为 !𝑠 𝑖!s i 的 Hash 值．

不断构造 𝑠 𝑖 =𝑠 𝑖−1 +!𝑠 𝑖−1 s i=s i−1+!s i−1．

𝑠 1 2 s 12 和 !𝑠 1 2!s 12 就是我们要的两个字符串．

推导

首先，有：

ℎ 𝑎 𝑠 ℎ 𝑖=ℎ 𝑎 𝑠 ℎ 𝑖−1⋅𝑏 𝑎 𝑠 𝑒 2 𝑖−2+!ℎ 𝑎 𝑠 ℎ 𝑖−1!ℎ 𝑎 𝑠 ℎ 𝑖=!ℎ 𝑎 𝑠 ℎ 𝑖−1⋅𝑏 𝑎 𝑠 𝑒 2 𝑖−2+ℎ 𝑎 𝑠 ℎ 𝑖−1 h a s h i=h a s h i−1⋅b a s e 2 i−2+!h a s h i−1!h a s h i=!h a s h i−1⋅b a s e 2 i−2+h a s h i−1

尝试相减：

ℎ 𝑎 𝑠 ℎ 𝑖−!ℎ 𝑎 𝑠 ℎ 𝑖= ℎ 𝑎 𝑠 ℎ 𝑖−1⋅𝑏 𝑎 𝑠 𝑒 2 𝑖−2+!ℎ 𝑎 𝑠 ℎ 𝑖−1−(!ℎ 𝑎 𝑠 ℎ 𝑖−1⋅𝑏 𝑎 𝑠 𝑒 2 𝑖−2+ℎ 𝑎 𝑠 ℎ 𝑖−1)= (ℎ 𝑎 𝑠 ℎ 𝑖−1−!ℎ 𝑎 𝑠 ℎ 𝑖−1)⋅(𝑏 𝑎 𝑠 𝑒 2 𝑖−2−1)h a s h i−!h a s h i= h a s h i−1⋅b a s e 2 i−2+!h a s h i−1−(!h a s h i−1⋅b a s e 2 i−2+h a s h i−1)= (h a s h i−1−!h a s h i−1)⋅(b a s e 2 i−2−1)

发现出现了 2 𝑖 2 i，但是原式太复杂，尝试换元：

设：

𝑓 𝑖=ℎ 𝑎 𝑠 ℎ 𝑖−!ℎ 𝑎 𝑠 ℎ 𝑖 𝑔 𝑖=𝑏 𝑎 𝑠 𝑒 2 𝑖−2−1 f i=h a s h i−!h a s h i g i=b a s e 2 i−2−1

根据原式得：

𝑓 𝑖=𝑓 𝑖−1⋅𝑔 𝑖=𝑓 1⋅𝑔 1⋅𝑔 2⋯𝑔 𝑖−1 f i=f i−1⋅g i=f 1⋅g 1⋅g 2⋯g i−1

因为 𝑏 𝑎 𝑠 𝑒 2 𝑖−2 b a s e 2 i−2 一定是奇数，所以 𝑔 𝑖 g i 一定是偶数．

所以：

2 𝑖−1|𝑓 𝑖 2 i−1|f i

但这样太大了，𝑖 −1 ≥6 4 i−1≥64 才能卡掉，继续化简：

𝑔 𝑖=𝑏 𝑎 𝑠 𝑒 2 𝑖−2−1=(𝑏 𝑎 𝑠 𝑒 2 𝑖−3−1)⋅(𝑏 𝑎 𝑠 𝑒 2 𝑖−3+1)g i=b a s e 2 i−2−1=(b a s e 2 i−3−1)⋅(b a s e 2 i−3+1)

即 𝑔 𝑖 g i 为 𝑔 𝑖−1 ⋅𝑐 (𝑐 ≡0(m o d 2))g i−1⋅c (c≡0(mod 2)) 的形式．

所以 2|𝑠 1 2|s 1，4|𝑠 2 4|s 2，……，即

2 𝑖|𝑔 𝑖 2 1⋅2 2⋅2 3⋯2 𝑖−1|𝑓 𝑖 2 𝑖(𝑖−1)/2|𝑓 𝑖 2 i|g i 2 1⋅2 2⋅2 3⋯2 i−1|f i 2 i(i−1)/2|f i

即当 𝑖 =1 2 i=12 时就可以使 2 6 4|ℎ 𝑎 𝑠 ℎ 𝑖 −!ℎ 𝑎 𝑠 ℎ 𝑖 2 64|h a s h i−!h a s h i 达到要求．

### 例题

例题：BZOJ 3097 Hash Killer I

给定一个用 自然溢出 实现的 Hash，要求构造一个字符串来卡掉它．

例题：BZOJ 3097 Hash Killer II

给定一个用 大模数 实现的 Hash，要求构造一个字符串来卡掉它．

例题：洛谷 U461211 字符串 Hash（数据加强）

给定 𝑛 n 个字符串，判断不同的字符串有多少个．

## Hash 的改进

### 多值 Hash

看了上面这么多的卡法，当然也有解决办法．

多值 Hash，就是有多个 Hash 函数，每个 Hash 函数的模数不一样，这样就能解决 Hash 冲突的问题．

判断时只要有其中一个的 Hash 值不同，就认为两个字符串不同，若 Hash 值都相同，则认为两个字符串相同．

一般来说，双值 Hash 就够用了．

### 多次询问子串哈希

单次计算一个字符串的哈希值复杂度是 𝑂(𝑛)O(n)，其中 𝑛 n 为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下．

一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个 𝑏 b 进制的数对 𝑀 M 取模的结果，这样的话每次就能快速求出子串的哈希了：

令 𝑓 𝑖(𝑠)f i(s) 表示 𝑓(𝑠[1..𝑖])f(s[1..i])，即原串长度为 𝑖 i 的前缀的哈希值，那么按照定义有 𝑓 𝑖(𝑠) =𝑠[1] ⋅𝑏 𝑖−1 +𝑠[2] ⋅𝑏 𝑖−2 +⋯ +𝑠[𝑖 −1] ⋅𝑏 +𝑠[𝑖]f i(s)=s[1]⋅b i−1+s[2]⋅b i−2+⋯+s[i−1]⋅b+s[i]

现在，我们想要用类似前缀和的方式快速求出 𝑓(𝑠[𝑙..𝑟])f(s[l..r])，按照定义有字符串 𝑠[𝑙..𝑟]s[l..r] 的哈希值为 𝑓(𝑠[𝑙..𝑟]) =𝑠[𝑙] ⋅𝑏 𝑟−𝑙 +𝑠[𝑙 +1] ⋅𝑏 𝑟−𝑙−1 +⋯ +𝑠[𝑟 −1] ⋅𝑏 +𝑠[𝑟]f(s[l..r])=s[l]⋅b r−l+s[l+1]⋅b r−l−1+⋯+s[r−1]⋅b+s[r]

对比观察上述两个式子，我们发现 𝑓(𝑠[𝑙..𝑟]) =𝑓 𝑟(𝑠) −𝑓 𝑙−1(𝑠) ×𝑏 𝑟−𝑙+1 f(s[l..r])=f r(s)−f l−1(s)×b r−l+1 成立（可以手动代入验证一下），因此我们用这个式子就可以快速得到子串的哈希值．其中 𝑏 𝑟−𝑙+1 b r−l+1 可以 𝑂(𝑛)O(n) 的预处理出来然后 𝑂(1)O(1) 的回答每次询问（当然也可以快速幂 𝑂(l o g⁡𝑛)O(log⁡n) 的回答每次询问）．

## 实现

### 模数 Hash：

注：效率较低，实际使用中不推荐．

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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);
    }

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

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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

## Hash 的应用

### 字符串匹配

求出模式串的哈希值后，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串的哈希值比较即可．

### 允许 𝑘 k 次失配的字符串匹配

问题：给定长为 𝑛 n 的源串 𝑠 s，以及长度为 𝑚 m 的模式串 𝑝 p，要求查找源串中有多少子串与模式串匹配．𝑠′s′ 与 𝑠 s 匹配，当且仅当 𝑠′s′ 与 𝑠 s 长度相同，且最多有 𝑘 k 个位置字符不同．其中 1 ≤𝑛,𝑚 ≤1 0 6 1≤n,m≤10 6，0 ≤𝑘 ≤5 0≤k≤5．

这道题无法使用 KMP 解决，但是可以通过哈希 + 二分来解决．

枚举所有可能匹配的子串，假设现在枚举的子串为 𝑠′s′，通过哈希 + 二分可以快速找到 𝑠′s′ 与 𝑝 p 第一个不同的位置．之后将 𝑠′s′ 与 𝑝 p 在这个失配位置及之前的部分删除掉，继续查找下一个失配位置．这样的过程最多发生 𝑘 k 次．

总的时间复杂度为 𝑂(𝑚 +𝑘 𝑛 l o g 2⁡𝑚)O(m+k n log 2⁡m)．

### 最长回文子串

二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等．需要分别预处理正着和倒着的哈希值．时间复杂度 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n)．

这个问题可以使用 manacher 算法 在 𝑂(𝑛)O(n) 的时间内解决．

通过哈希同样可以 𝑂(𝑛)O(n) 解决这个问题，具体方法就是记 𝑅 𝑖 R i 表示以 𝑖 i 作为结尾的最长回文的长度，那么答案就是 m a x 𝑛 𝑖=1 𝑅 𝑖 max i=1 n R i．考虑到 𝑅 𝑖 ≤𝑅 𝑖−1 +2 R i≤R i−1+2，因此我们只需要暴力从 𝑅 𝑖−1 +2 R i−1+2 开始递减，直到找到第一个回文即可．记变量 𝑧 z 表示当前枚举的 𝑅 𝑖 R i，初始时为 0 0，则 𝑧 z 在每次 𝑖 i 增大的时候都会增大 2 2，之后每次暴力循环都会减少 1 1，故暴力循环最多发生 2 𝑛 2 n 次，总的时间复杂度为 𝑂(𝑛)O(n)．

### 最长公共子字符串

问题：给定 𝑚 m 个总长不超过 𝑛 n 的非空字符串，查找所有字符串的最长公共子字符串，如果有多个，任意输出其中一个．其中 1 ≤𝑚,𝑛 ≤1 0 6 1≤m,n≤10 6．

很显然如果存在长度为 𝑘 k 的最长公共子字符串，那么 𝑘 −1 k−1 的公共子字符串也必定存在．因此我们可以二分最长公共子字符串的长度．假设现在的长度为 𝑘 k，`check(k)` 的逻辑为我们将所有所有字符串的长度为 𝑘 k 的子串分别进行哈希，将哈希值放入 𝑛 n 个哈希表中存储．之后求交集即可．

时间复杂度为 𝑂(𝑚 +𝑛 l o g⁡𝑛)O(m+n log⁡n)．

### 确定字符串中不同子字符串的数量

问题：给定长为 𝑛 n 的字符串，仅由小写英文字母组成，查找该字符串中不同子串的数量．

为了解决这个问题，我们遍历了所有长度为 𝑙 =1,⋯,𝑛 l=1,⋯,n 的子串．对于每个长度为 𝑙 l，我们将其 Hash 值乘以相同的 𝑏 b 的幂次方，并存入一个数组中．数组中不同元素的数量等于字符串中长度不同的子串的数量，并此数字将添加到最终答案中．

为了方便起见，我们将使用 ℎ[𝑖]h[i] 作为 Hash 的前缀字符，并定义 ℎ[0] =0 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();

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

### 例题

CF1200E Compress Words

给你若干个字符串，答案串初始为空．第 𝑖 i 步将第 𝑖 i 个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 𝑖 i 个串的前缀的字符串），求最后得到的字符串．

字符串个数不超过 1 0 5 10 5，总长不超过 1 0 6 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
    81
    82
    83
    84
    #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() {  // 初始化
        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() {
      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;
    }

本页面部分内容译自博文 строковый хеш 与其英文翻译版 String Hashing．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/2/2 11:53:55，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, ouuan, Tiphereth-A, 1292224662, Enter-tainer, Xeonacid, ShuYuMo2003, c-forrest, iamtwz, ksyx, mgt, taodaling, Yanjun-Zhao, algoriiiiithm, Chrogeek, GldHkkowo, Haohu Shen, HeRaNO, ImpleLee, kenlig, kevincoding03-rgb, Marcythm, Menci, Molmin, runnableAir, ScrapW, shawlleyw, sshwy, szdytom, tfia, wangchong, wendajiang, xglight, xiangmy21, zyouxam
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用