- 回忆：哈希函数与哈希冲突
- 哈希函数：将关键字映射成对应的地址的函数，记为
Hash(key) = Addr。 - 哈希冲突：哈希函数可能会把两个或两个以上的不同关键字映射到同⼀地址，这种情况称为哈希冲突。
- 字符串哈希
定义⼀个把字符串映射到整数的函数hash ，这就是字符串哈希。说⽩了，就是将⼀个字符串⽤⼀个整数表⽰。 - 字符串哈希中的哈希函数
在字符串哈希中，有⼀种冲突概率较⼩的哈希函数，将字符串映射成p 进制数字
h a s h ( s ) = ∑ i = 0 n − 1 s [ i ] × p n − i − 1 ( M O D M ) hash(s) = \sum^{n-1}_{i=0} s[i] \times p^{n-i-1} (MOD M) hash(s)=i=0∑n−1s[i]×pn−i−1(MODM)
其中，p通常取质数131或者13331。如果把哈希值定义为unsigned long long类型，在C++中，溢出就会⾃动取模。
但是，实际求哈希值时，我们⽤的是前缀哈希的思想来求，这样会和下⾯的多次询问⼦串哈希⼀致 - 前缀哈希数组
单次计算⼀个字符串的哈希值复杂度是O(N)。如果需要多次询问⼀个字符串的⼦串的哈希值，每次重新计算效率⾮常低下。
⼀般利⽤前缀和思想先预处理字符串中每个前缀的哈希值，这样的话每次就能快速求出⼦串的哈希了
typedef unsigned long long ULL;
const int N = 1e6 + 10, P = 13331;
char s[N];
int len;
ULL f[N]; // 前缀哈希数组
ULL p[N]; // 记录 p 的 i 次⽅
// 处理前缀哈希数组以及 p 的 i 次⽅数组
void init_hash()
{ f[0] = 0; p[0] = 1; for(int i = 1; i <= len; i++) { f[i] = f[i - 1] * P + s[i]; p[i] = p[i - 1] * P; }
}
// 快速求得任意区间的哈希值
ULL get_hash(int l, int r)
{return f[r] - f[l - 1] * p[r - l + 1];
}
如果题⽬只是简单的求单个字符串的哈希值：
typedef unsigned long long ULL;
const int N = 1e6 + 10;
int len;
char s[N];
ULL gethash()
{ ULL ret = 0; for(int i = 1; i <= len; i++) { ret = ret * p + s[i]; } return ret;
}
P3370 【模板】字符串哈希 - 洛谷
#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ULL;const int N = 1e4 + 10, P = 131;int n;
int a[N];ULL get_hash(string& s)
{ULL ret = 0;for (int i = 1; i <= s.size(); i++){ret = ret * P + s[i-1]; }return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++){string s; cin >> s;a[i] = get_hash(s);}int ret = 1;sort(a+1, a+1+n);for (int i = 2; i <= n; i++){if (a[i] != a[i-1]) ret++; }cout << ret << endl;return 0;
}
P10468 兔子与兔子 - 洛谷
#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ULL;const int N = 1e6 + 10, P = 13331;int n;
string s;
ULL f[N]; //前缀哈希数组
ULL p[N]; //p的i次方void init_hash()
{p[0] = 1;for (int i = 1; i <= n; i++){f[i] = f[i-1] * P + s[i];p[i] = p[i-1] * P;}
}ULL get_hash(int l, int r)
{return f[r] - f[l-1] * p[r-l+1];
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> s;n = s.size();s = " " + s;init_hash();int m; cin >> m;while (m--){int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;ULL x = get_hash(l1, r1), y = get_hash(l2, r2);if (x == y) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}
)
介绍，附pdf)
