Songbirds


春

字符串Hash

  • ~3.84K 字
  1. 1. 1.字符串Hash原理
  2. 2. 2.双Hash取模

字符串的匹配算法之一，字符串匹配个人觉得比较复杂，所以单独写一篇

字符串查找算法中，一个很重要的算法是KMP，但是KMP的理解与记忆还是比较困难的。
而字符串Hash算法则是一种比较容易简单的算法。但是字符串Hash算法仍然有其缺陷，就是Hash冲突的存在，无论怎么处理，冲突的概率只会降低，不会完全消失。但好在，一般的题目降低到较低的冲突概率即可AC。

1.字符串Hash原理

我们要在一个主串中查找一个模式串，则模式串的长度是已知的为n。字符串Hash的本质原理是枚举所有长度为n的子串的Hash值。所以如何能够快速的求出以left为起点，right为结束点，长度为n的字符串的Hash值。是最为关键的。
字符串Hash使用进制思想求出Hash值，使用前缀和以O(1)的时间求出left到right的Hash值。

对于字符串abc，计算Hash值时，我们将其转换为一个p进制数，其Hash值计算如下(未取模)：

a=a的ASCII码值∗p0ab=a的ASCII码值∗p1+b的ASCII码值∗p0abc=a的ASCII码值∗p2+b的ASCII码值∗p1+c的ASCII码值∗p0\begin{aligned} a &= a的ASCII码值 * p^0\\ ab &= a的ASCII码值 * p^1 + b的ASCII码值 * p^0\\ abc &= a的ASCII码值 * p^2 + b的ASCII码值 * p^1 + c的ASCII码值 * p^0\\ \end{aligned}

则字符串bc的Hash快速取值如下：

bc=b的ASCII码值∗p1+c的ASCII码值∗p0=abc−a∗p2\begin{aligned} bc = b的ASCII码值 * p^1 + c的ASCII码值 * p^0 = abc - a * p^2 \end{aligned}

具体的我们可以有：

Hash[left到right]=Hash[right]−Hash[left−1]∗pArr[right−left+1]Hash[left到right] = Hash[right] - Hash[left - 1] * pArr[right - left + 1]

于是我们可以开辟两个数组，一个存储到下标1到下标i的Hash值，一个是下标i的进制值幂次结果。

1
2
3
4
5
6
7
8
9
10
// 注意字符串的下标从1开始，我们的两个数组意义上也从1开始
p[0] = 1; // 存储进制的幂次结果，p[0]不代表字符，由于是幂次，p^0 = 1;
h[0] = 0; // 存储下标1到i的Hash值，所以0只能初始化0.
// 这里的示例我们给131进制
for (int i = 1; i <= s.length(); i++) {
    h[i] = h[i - 1] * 131 + s.charAt(i - 1); // 对于第i个字符，其下标是i-1
    p[i] = p[i - 1] * 131;
}
// 对于下标left 到right 之间的字符Hash,left <= right
h[left到right] = h[right] - hash[left - 1] * P[right - left + 1];

2.双Hash取模

单Hash取模，就是只模一次，比双模冲突的概率高一点。节省版面，只介绍双hash取模。

所谓的双Hash取模，即只取两次模。进制质数：131，13331 ； 取模质数： 1e9 + 7，1e9 + 9。
这几个数都是经验值。两种数都取质数，能显著降低冲突。
同时取模质数应该尽可能的大。同时数组要开long数组，避免溢出变为负数的情况。还要使用同余定理，避免求left到right减出负数的情况。

模板题：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

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
class Solution {
    public int strStr(String haystack, String needle) {
        long mod1 = (int) (1e9 + 7);
        long mod2 = (int) (1e9 + 9);
        long p1 = 131L;
        long p2 = 13331L;

        int n = haystack.length();
        // long数组
        long[] hArr1 = new long[n + 1];
        long[] hArr2 = new long[n + 1];
        long[] pArr1 = new long[n + 1];
        long[] pArr2 = new long[n + 1];

        hArr1[0] = 0;
        hArr2[0] = 0;
        pArr1[0] = 1;
        pArr2[0] = 1;
        // 第一个字符记为1，所以到等于n结束
        // 处理Hash与进制的幂次
        for (int i = 1; i <= n; i++) {
            // 下标为i时，找的是i-1个字符
            hArr1[i] = ((hArr1[i - 1] * p1) % mod1 + haystack.charAt(i - 1)) % mod1;
            hArr2[i] = ((hArr2[i - 1] * p2) % mod2 + haystack.charAt(i - 1)) % mod2;

            pArr1[i] = (pArr1[i - 1] * p1) % mod1;
            pArr2[i] = (pArr2[i - 1] * p2) % mod2;
        }

        int k = needle.length();
        long ansHash1 = 0L;
        long ansHash2 = 0L;
        // 计算要匹配字符串的Hash值
        for (int i = 1; i <= k; i++) {
            ansHash1 = ((ansHash1 * p1) % mod1 + needle.charAt(i - 1)) % mod1;
            ansHash2 = ((ansHash2 * p2) % mod2 + needle.charAt(i - 1)) % mod2;
        }

        // 根据前缀Hash枚举所有Hash，i从1开始。原因见上面
        for (int i = 1; i <= n - k + 1; i++) {
            int left = i;
            int right = i + k - 1;

            long tempHash1 = hArr1[right] - hArr1[left - 1] * pArr1[right - left + 1];
            // (-x % mod + mod) % mod 同余定理，避免减出负数的情况,。如果是正数，与该公式结果相同
            tempHash1 = (tempHash1 % mod1 + mod1) % mod1;

            long tempHash2 = hArr2[right] - hArr2[left - 1] * pArr2[right - left + 1];
            tempHash2 = (tempHash2 % mod2 + mod2) % mod2;

            if (tempHash1 == ansHash1 && tempHash2 == ansHash2) {
                return i - 1;
            }
        }

        return -1;
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可