本文改编自https://blog.csdn.net/pengwill97/article/details/80879387


        很多题目涉及字符串问题，但是字符串不如整数那样容易处理，尤其是涉及图时。这时需要构造映射string->int来将字符串转化为int，这就是字符串哈希算法。

        哈希方案有很多种，这里选择很常用的一个—BKDR Hash。
        哈希思路是将字符串看成是一个base位进制数(base为一个大质数)，具体思路如下:
        对于字符串的第i位，有:

        最后一个算出的hash值作为整个字符串的哈希值。
        P是一个大于base的质数。hash为一个unsigned long long的数组。
        容易看出这是计算这个base进制数的公式并且每个值都对P取了模，这个方法可以将字符串映射到[0，P)的正整数。
        但是可能有两个字符串不同但哈希值相同的情况，称为哈希冲突。在base，P足够大时这种冲突概率很低。
这里列举几个质数，读者可以参考使用。

素数 冲突率%
53 10.416667
97 1.0416670
193 0.520833
389 1.302083
769 0.130208
1543 0.455729
3079 0.227865
6151 0.113932
12289 0.008138
24593 0.069173
49157 0.010173
98317 0.013224
196613 0.002543
393241 0.006358
786433 0.000128
1572869 0.000318
3145739 0.000350
6291469 0.000207
12582917 0.000040
25165843 0.000075
50331653 0.000010
100663319 0.000023
201326611 0.000009
402653189 0.000001
805306457 0.000011
1610612741 0.000000

        洛谷P3370用字符串哈希求互异字符串个数，下面给出代码:

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
#include<iostream>

using namespace std;
const int P1 = 19260817, P2 = 100663319;
int vis[P2] = {0};
unsigned long long h[1050] = {0};

inline int Hash(string s) {
    h[0] = s[0] - 'a' + 1;
    for (int i = 1; i < s.length(); i++) {
        h[i] = (h[i - 1] * P1 + s[i] - 'a' + 1) % P2;
    }
    return h[s.length() - 1];
}

int main() {
    ios::sync_with_stdio(false);
    int n, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        int h = Hash(str);
        if (vis[h] == 0)vis[h] = 1, ans++;
    }
    cout << ans;
    return 0;
}

子串的哈希

        只哈希一整个字符串并没有什么卵用，我们必须找到一种方法可以很快地哈希子串。
        这里有一种预处理复杂度为$O(n)$，查询复杂度为$O(1)$的子串哈希算法。
        首先，用一个$hs$数组记录哈希值，假设字符串下标从0开始，那么可以用下面的递推公式推出哈希值：

        这里为了增强适用性，不再将字符减去$’a’$，BASE的含义与上文基本相同，这里可以取一个小质数，比如23。
        对于$hs$数组，将其定义为unsigned long long类型，使其自然溢出，这样撞车的概率很低。
        那么问题来了，如何根据$hs$数组找到某一段子串（$[l,r]$）的哈希值？
        考虑一下下面的几个值：

        规律应该很明显了，$[l,r]$的哈希值就是：

        这样再预处理出$BASE$的幂次，就可以$O(1)$求所有子串的哈希值了。子串哈希的一个应用是在$O(logn)$复杂度下对比两个子串的字典序大小。
        我们只需要二分一个长度$mid$，对比两个子串在前$mid$位置的哈希值，就能找到两个串第一个不同的位置，然后就可以轻松地判别两个串的字典序大小。