字符串哈希

字数统计: 2.5k字 | 阅读时长: 10分

169

2020-11-12

摘要: 本文系统梳理了字符串哈希相关的要点，并通过字符串精确匹配问题给出代码模板。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们系统串讲一下字符串哈希算法。字符串哈希的哈希函数把任意长度的字符串 s (可以推广到数组 vec)，映射成一个非负整数，并且冲突概率极低。

这种应用哈希算法来解决字符串匹配问题的算法，是 Rabin是和是 Karp是在是 1980是年代初期，因此也称为 RK 算法。

首先介绍两个常用的哈希函数，然后研究如何对子串的哈希值进行高效处理，有前缀的方式和滚动的方式两种，其中前缀的方式有力扣 1392 和 1316 两道经典题，滚动方式处理的有力扣 686 经典题，最后要注意处理好溢出的情况。最后以字符串精确匹配为模板题，给出前缀处理和滚动处理两种计算子串哈希值的方法的代码模板。

本文内容总览如下：

哈希函数
- p 进制数
- 直接求和
子串的哈希值
- 前缀方式处理
  - 1392. 最长快乐前缀
  - 1316. 不同的循环子字符串
- 滚动方式处理
  - 686. 重复叠加字符串匹配
避免溢出
- 取模
- 自然溢出
模板题
- 字符串精确匹配

要点1：哈希函数

字符串哈希函数有很多主流的设计方式，参考文章字符串哈希的哈希函数，这里介绍最简单的两种，一般的问题够用。

哈希函数1：p 进制数

取一个固定值 p（一般取质数），对于字符串 s，长度为 m，则将 s 视为 m 位 p 进制数。给每个字符分配一个整数代表该字符，一般分配的字符都远小于 p。p 常用 131, 13331。

这样长为 m 的字符串 s 的哈希值就是该 m 位 p 进制数：

$\begin{align} hash(s) & = s[0] * p^{m-1} + s[1] * p^{m-2} + ... \\ & \quad\quad + s[m-2] * p^{1} + s[m-1] * p^{0} \\ & = \sum_{j=0}^{m-1}s[j]p^{m-1-j} \end{align}$

如果是很长的字符串 s 中的一个长为 m 的窗口 s[i..i+m-1]，哈希函数 $hash(s[i..i+m-1])$ 如下：

$hash(s[i..i+m-1]) = \sum_{j=0}^{m-1}s[i + j]p^{m-1-j}$

生成一个长度为 m 的字符串的哈希码，需要 $O(m)$ 时间。

取一个固定值 MOD，求出的值对 MOD 取模，作为 s 最终的哈希值。

如果 MOD = $2^{64}$ ，可以直接用 unsigned long long 存储哈希值，自动对 $2^{64}$ 取模，这种方法叫自然溢出。

哈希函数2：直接求和

直接将字符串中各个字母映射到 0~25 之后相加作为哈希值。相当于第一个哈希函数中 p 取 1 的情况。

长为 m 的字符串 s 的哈希函数：

$hash(s) = \sum_{j=0}^{m-1}s[j] \\$

很长的字符串 s 中的一个长为 m 的窗口的哈希函数：

$hash(s[i..i+m-1]) = \sum_{j=0}^{m-1}s[i+j] \\$

生成一个长度为 m 的字符串的哈希码，依然需要 $O(m)$ 时间。

这种方法代码简单，不容易出错，但是比第一个函数容易冲突。

要点2：子串的哈希值

用字符串哈希算法做字符串精确匹配还有一个关键问题要解决：摊销 $O(1)$ 地生成各个窗口的哈希码，有两种办法，一种是滚动的方式处理，一种是前缀的方式处理。

前缀方式处理

将 s 中的每个前缀对应的哈希值先预处理出来，记录在 prefix_hash 中。

当 i = 0 时，prefix_hash[i] = 0，表示空前缀的哈希值，
当 i > 0 时，prefix_hash[i] := 前缀 s[0..i-1] 的哈希值。

推 prefix_hash 的过程与推前缀和的过程很像，如下：

vector<unsigned long long> prefix_hash(n + 1, 0);
vector<unsigned long long> pp(n + 1, 0); 
pp[0] = 1;
for(int i = 1; i <= n; ++i)
{
    prefix_hash[i] = prefix_hash[i - 1] * p + s[i - 1];
    pp[i] = pp[i - 1] * p;
}

代码中 pp 用于维护 p 的幂：pp[i]:= p 的 i 次幂，其中 pp[0] = 1。

利用 prefix_hash 可以 O(1) 地求出 s 上任意子串的哈希值，这一点类似前缀和。例如当前窗口 [l, r] 上的哈希值如下, 其中窗口长度为 len：

1	unsigned long long hash = (prefix_hash[r] - prefix_hash[l - 1] * pp[len]);

例题：

滚动方式处理

利用滑动窗口的特性，每次滑动都有一个元素进，一个元素出。因此当窗口前进一位的时候。

考虑当前窗口，窗长为 len，起点为 i，上一个窗口的起点为 i - 1，上一个窗口的哈希值为 hash_substr，新的窗口中删除了元素 s[i-1]，增加了 s[i+len-1]，因此只需要在上一个窗口的哈希值 hash_substr 的基础上，处理删除和增加的两个字符对哈希值的贡献即可。

以哈希函数2 为例：

1
2
3

hash_substr = hash_substr - s[i - len] * pp[len];
hash_substr = hash_substr * p;
hash_substr = hash_substr + s[i];

例题：

686. 重复叠加字符串匹配

要点3：避免溢出

pp[i] 可能是很大的数字，需要通过取模 MOD 的方式设置一个上限，用 hash % MOD 代替原来的哈希值 hash。

具体有两种方式：

一种是将 hash 值的类型设为 unsigned long long，若出现溢出，相当于自动模了 $2^{64}$ 。
另一种是设一个 MOD 的值，在计算哈希值的各个中间环节中都取模，避免溢出。

总结

字符串哈希算法关键的三点，哈希函数，子串的哈希值，避免溢出

模板题：字符串精确匹配

28. 实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

提示：

1 2	1 <= haystack.length, needle.length <= 1e4 haystack 和 needle 仅由小写英文字符组成

示例 1：
输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：”sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

算法：字符串哈希

用字符串哈希做精确匹配也称 Rabin Karp 算法。

对 pattern 生成一个哈希值。对 s 中的每个长度为 m 的窗口(即 BF 算法中枚举的子串)生成一个哈希值。

对两个哈希值作比较，如果哈希值不相等，则当前窗口与 p 一定不匹配，如果哈希值相等，则当前窗口与 p 可能匹配，也可能不匹配（发生哈希冲突的情况），需要对当前窗口和 p 进行一次逐一比较进行确认。逐一比较确认的目的是排除两个长为 m 的不同字符串哈希值相同，即哈希冲突的情况。

BF 算法（参考文章字符串精确匹配）中每个窗口都要做逐一比较，而字符串哈希的方法只有哈希值相等的时候才会做逐一比较。

代码1 (C++，模板，前缀法)

模板：哈希函数1 + 前缀哈希 + 预处理 $p^{i}$

p, mod 的质数选取: 201326611, 402653189, 1610612741。

class Solution {
public:
    int strStr(string s, string pattern) {
        if(pattern.empty()) 
            return 0;
        if(s.empty()) 
            return -1;
        int n = s.size(), m = pattern.size();
        if(n < m) 
            return -1;

        // n > 0, m > 0, n >= m
        const int MOD = 1610612741;
        const int p = 201326611;
        using ll = long long;

        // 主串的前缀哈希数组
        vector<ll> prefix_hash(n + 1, 0);
        vector<ll> pp(n + 1, 0); // 使用 MOD 的时候不能用 unsigned long long
        pp[0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            prefix_hash[i] = (prefix_hash[i - 1] * p + (s[i - 1] - 'a')) % MOD;
            pp[i] = (pp[i - 1] * p) % MOD;
        }

        // 模式串的哈希值
        ll pattern_hash = 0;
        for(int i = 0; i < m; ++i)
            pattern_hash = (pattern_hash * p + (pattern[i] - 'a')) % MOD;

        // 长度为 m 的子串, hash数组中对应位置 [l, r] -- [1..n-m+1, m..n]
        // p 的幂，只需要 m - 1 次
        for(int i = 1; i <= n - m + 1; ++i)
        {
            int l = i, r = i + m - 1;
            ll hash = ((prefix_hash[r] - prefix_hash[l - 1] * pp[m]) % MOD + MOD) % MOD;
            if(hash == pattern_hash)
            {
                int start = i - 1;
                int j = 0;
                while(j < m && s[start + j] == pattern[j])
                    j++;
                if(j == m)
                    return start;
            }
        }
        return -1;
    }
};

代码2 (C++，模板，滚动法)

哈希函数1 + 滚动哈希 + 预处理 $p^{i}$

class Solution {
public:
    int strStr(string s, string pattern) {
        if(pattern.empty()) 
            return 0;
        if(s.empty()) 
            return -1;
        int n = s.size(), m = pattern.size();
        if(n < m) 
            return -1;

        // n > 0, m > 0, n >= m
        const int MOD = 1610612741;
        const int p = 201326611;
        using ll = long long;

        // 模式串的哈希值
        ll pattern_hash = 0;
        for(int i = 0; i < m; ++i)
            pattern_hash = (pattern_hash * p + (pattern[i] - 'a')) % MOD;

        // p 的幂，只需要 m - 1 次
        vector<ll> pp(m, 0); // 使用 MOD 的时候不能用 unsigned long long
        pp[0] = 1;
        ll hash_substr = 0;
        for(int i = 0; i < m; ++i)
        {
            hash_substr = (hash_substr * p + (s[i] - 'a')) % MOD;
            if(i > 0)
                pp[i] = (pp[i - 1] * p) % MOD;
        }
        if(hash_substr == pattern_hash)
        {
            int i = 0;
            while(i < m && s[i] == pattern[i])
                i++;
            if(i == m)
                return 0;
        }
        // 开始滚动
        for(int i = m; i < n; ++i)
        {
            int start = i - m + 1;
            hash_substr = ((hash_substr - (s[start - 1] - 'a') * pp[m - 1]) % MOD + MOD) % MOD;
            hash_substr = (hash_substr * p) % MOD;
            hash_substr = (hash_substr + (s[i] - 'a')) % MOD;
            if(hash_substr == pattern_hash)
            {
                int j = 0;
                while(j < m && s[start + j] == pattern[j])
                    j++;
                if(j == m)
                    return start;
            }
        }
        return -1;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法字符串