通俗易懂的字符串哈希算法，你确定不来看一下吗?

ゝ一纸荒年。 2022-11-03 11:06 150阅读 0赞

**上一篇博客：[C++ STL详解（4）][C_ STL_4]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  简介
 *  如何求哈希值
 *  如何求子串的哈希值
 *  如何使用字符串哈希值
 *  例题
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  数据范围
         *  输入样例
         *  输出样例
     *  题解
     *   *  解题代码

# 简介 #

**字符串哈希** 也叫做 **字符串前缀哈希法** 就是将预先一个字符串的每一个前缀都映射成一个 `哈希值`，当需要判断两个 `子字符串` 是否一样时，只需要判断这两个子字符串的哈希值是否相同就可以了。这样就可以通过 **O(n)** 的时间预处理字符串所有前缀 `Hash` 并在 **O(1)** 的时间内查询它的任意子串的 Hash 值。

# 如何求哈希值 #

首先取一个固定值 **P** ，将字符串看做是一个 **P** 进制的数，并分配一个大于 **0** 的数值代表每一个字符（为了方便直接用ASCII码也可以）。一般来说分配的数值都远小于 **P**。再取一个固定值 **M**，求出该 **P** 进制的数对 **M** 取模所得到的余数，作为字符串的哈希值。

一般将 **P** 的值取为 `131` 或者 `13331`，此时 Hash 值产生的冲突值极低，基本可以认为没有冲突，可以认为对于每一个不同的字符串，它们的哈希值都是唯一的。通常使 M =  2 64 2^\{64\} 264, 直接使用 **unsigned long long** 类型存储这个 Hash 值， 在计算时不处理算术溢出问题，产生溢出时相当于自动对  2 64 2^\{64\} 264 取模，这样可以避免低效的取模 (mod) 运算。\[1\]

# 如何求子串的哈希值 #

这个方法类似 **前缀和** 的思想：开一个**unsigned long long** 类型的数组 **h\[\]** 来存储字符串 **str** 的哈希值。其中 **h\[i\]** 存储的是前 **i** 位字符串的哈希值。当求第 **i + 1** 位字符串的哈希值时，只需要使 **h\[i - 1\] \* p + str\[i\]** 即可。因为 第 **i** 位是 最低位，它应当乘以  P 0 P^0 P0，又因为  P 0 = 1 P^0 = 1 P0=1 ，所以直接省略即可。

**h\[i - 1\] \* p + str\[i\]** 相当于将前 **i - 1** 位每一位都乘了一个 **P**，将所有的位抬高了一位，然后再加上最低位。就像是十进制的 **123**，如何将其变为 **1234** 呢？直接将  123 ∗ 10 123 \* 10 123∗10 将其变为 **1230**， 把原来的个十百位都依次往后抬高一位，将 **个位** 空出来加上 **4** 即可。

# 如何使用字符串哈希值 #

我们以 **O(n)** 的时间复杂度预处理完所有的子字符串的哈希值之后想要求某一段的哈希值怎样求呢？首先以十进制来进行举例：在 **1234** 中怎样算出第 **2 ~ 3** 位即 **23** 的值呢？

假设已经将十进制 **1234** 的前缀值预处理完毕，已经存储到了 **h\[\]** 数组中。那么此时 **h\[i\]** 存储的就是前 **i** 位的值即 **h\[1\] = 1; h\[2\] = 12; h\[3\] = 123; h\[4\] = 1234**。可以发现要求的第 **2 ~ 3** 的值 **23** 与 **h\[3\]** 和 **h\[1\]** 有关。在 **h\[3\] = 123** 中的 **1** 是百位，而在 **h\[1\] = 1** 中的 **1** 是个位，如果直接用 **h\[3\] - h\[1\]**,当然不会得到正确的结果。我们需要先将 **h\[1\]** 中的 **1** 变为百位，使之与 **h\[3\]** 中的 **1** 级别一样才可以得到正确的结果。即 **h\[3\] - h\[1\]  ∗   1 0 2 = 23 \* \\ 10^2 = 23 ∗ 102=23**。

为了方便快速的求出相减时抬高位数所需要乘的数，可以在预处理时同时使用一个数组 **p\[\]** 来预处理出乘以 **P** 的多少次方，比如 **p\[1\]** 中存储乘以  p 1 p^1 p1，**p\[2\] = p\[1\]  ∗ \* ∗ p** 表示乘以  p 2 p^2 p2。递推公式为：**p\[i\] = p\[i -1\]  ∗ \* ∗ p**。

通过上面的解释就可以很轻松的理解如何求出 **P** 进制的字符串哈希值的任意子串的哈希值了。比如已经将字符串所有前缀的哈希值存到了 **h\[\]** 数组中，那么 **L ~ R** 区间的子字符串的哈希值为：**h\[R\] - h\[L - 1\]  ∗ \* ∗ p\[R - L + 1\]**。

# 例题 #

题目来源：[ACWing 841. 字符串哈希][ACWing 841.]

## 题目信息 ##

### 题目描述 ###

给定一个长度为 **n** 的字符串，再给定 **m** 个询问，每个询问包含四个整数**l1,r1,l2,r2**，请你判断 **\[l1,r1\]** 和 **\[l2,r2\]** 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

### 输入格式 ###

第一行包含整数 **n** 和 **m**，表示字符串长度和询问次数。

第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。

接下来 **m** 行，每行包含四个整数 **l1,r1,l2,r2**，表示一次询问所涉及的两个区间。

注意，字符串的位置从1开始编号。

### 输出格式 ###

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 **“Yes”**，否则输出 **“No”**。

每个结果占一行。

### 数据范围 ###

1 ≤ n, m ≤  1 0 5 10^5 105

### 输入样例 ###

> **8 3  
> aabbaabb  
> 1 3 5 7  
> 1 3 6 8  
> 1 2 1 2**

### 输出样例 ###

> **Yes  
> No  
> Yes**

## 题解 ##

### 解题代码 ###

#include<iostream>
    using namespace std;
    
    const int N = 100010, base = 131;
    typedef unsigned long long ULL;
    ULL h[N], p[N];
    char str[N];
    
    ULL getHash(int l, int r) { 
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    
    int main() { 
        int n, m;
        cin >> n >> m;
        scanf("%s", str + 1); // 从下标为 1 的位置开始存
        p[0] = 1;
        for (int i = 1; i <= n; i++) { 
            p[i] = p[i - 1] * base;
            h[i] = h[i - 1] * base + str[i];
        }
        while (m--) { 
            int l1, r1, l2, r2;
            scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
            if (getHash(l1, r1) == getHash(l2, r2)) puts("Yes");
            else puts("No");
        }
        return 0;
    }

--------------------

参考资料：\[1\]《算法竞赛进阶指南》

--------------------

> 未完待续，持续更新中……  
> ![20210227224152262.png][]

[C_ STL_4]: https://ac-fun.blog.csdn.net/article/details/113939257
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[ACWing 841.]: https://www.acwing.com/problem/content/843/
[20210227224152262.png]: /images/20221024/f4d45bac317e40c1bb00f16ae1bb9c4a.png