- 【用途】加密、判斷字串相同、樹同構、陣列內容相等。
- 【做法】
- 資料經過運算 (hash function) 對應到某個整數
- 一樣的資料經過相同的hash運算，會對應到相同的整數
- 無法輕易從hash值回推出原始資料
- 要避免 hash 碰撞 (collision)
- 【實作】Rolling Hash
- 定義兩個質數，一小一大
- mul：小質數，例如 37
- mod：大質數，例如 1e9 + 7
- Hash = 0; Hash *= mul; Hash += i; Hash %= mod;
【例1】對陣列內容進行hash
- a[ ] = {1, 2, 3, 4, 5} –> {1, 39, 1446, 53506, 1979727}
- 1 = ( 1 ) % 10000007
- 39 = ( 1 * 37 + 2 ) % 10000007
- 1446 = ( 1 * 37^2 + 2 * 37 + 3 ) % 10000007
//【例1】對陣列內容進行hash
#include <iostream>
using namespace std;
const int mul = 37, mod = 1e9 + 7;
int main() {
int a[] = {1, 2, 3, 4, 5};
long long Hash = 0;
for (auto i: a){
Hash *= mul;
Hash += i;
Hash %= mod;
cout << Hash << ' ';
}
return 0;
}
【例2】對字串進行hash
- s = “abcde” –> {97, 3687, 136518, 5051266, 186896943}
//【例2】對字串進行hash
#include <iostream>
using namespace std;
const int mul = 37, mod = 1e9 + 7;
int main() {
string s = "abcde";
long long Hash = 0;
for (auto i: s){
Hash *= mul;
Hash += (int) i; //轉成 ASCII code
Hash %= mod;
cout << Hash << ' ';
}
return 0;
}
【例3】對樹進行hash (搭配 DFS)
- 下圖例的兩棵樹的 hash 都是 2813。 亦即兩棵樹同構。
- (Line-16) 要先排序
//【例3】對樹進行hash (搭配 DFS)
#include <iostream>
#include <vector>
using namespace std;
const int mul = 37, mod = 1e9 + 7;
const int maxn = 10;
vector <int> g[maxn];
int dfs(int now, int pre){
vector <int> v;
for (auto i: g[now]){
if(i != pre){
v.push_back(dfs(i, now));
}
}
sort(v.rbegin(), v.rend()); //由大排到小，避免碰撞
long long ret = 1; //如果是葉節點，會回傳 1
for (auto i: v){
ret *= mul;
ret += i;
ret %= mod;
}
return ret;
}
int main() {
int n, a, b;
cin >> n;
for (int i=0; i<n-1; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
cout << dfs(0, -1) << endl;
for (int i=0; i<n; i++){
g[i].clear();
}
for (int i=0; i<n-1; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
cout << dfs(5, -1) << endl;
return 0;
}
【例4】子字串 hash
- 對一個字串，多次查詢子字串的 hash 值
- 先計算每個 prefix hash 的結果，在進行 rolling hash 時順便紀錄。接著利用這些 prefix 的結果，湊出需要的 substring。
- 時間複雜度：
- 【EX】s = “abcdefg”
- pre[ ]：prefix hash 的結果
- pre[0] = 0
- pre[1] = (pre[0] + ‘a’) % mod
- pre[2] = (pre[1]* mul + ‘b’) % mod
- pre[3] = (pre[2]* mul + ‘c’) % mod
- pre[4] = (pre[3]* mul + ‘d’) % mod
- pre[5] = (pre[4]* mul + ‘e’) % mod
- substring [l, r] hash值：
- pre[r] – pre[l – 1] * (mul^(r – l + 1))
- Example: “cd” (3~4) hash值
- pre[4] = a * mul^3 + b * mul^2 + c * mul + d
- pre[3-1] = pre[2] = a * mul + b
- pre[2] * mul^2 = a * mul^3 + b * mul^2
- pre[4] – pre[2] * mul^2 = c * mul + d
//【例4】子字串 hash
#include <iostream>
#include <vector>
using namespace std;
const int mul = 37, mod = 1e9 + 7;
int pre[10];
int query(int l, int r){
long long ret = pre[l-1];
for (int i=0; i<r-l+1; i++){
ret *= mul;
ret %= mod;
}
return pre[r] - ret;
}
int main() {
string s = "abcdefg";
pre[0] = 0;
long long Hash = pre[0];
for (int i=1; i<=s.size(); i++){
Hash *= mul;
Hash += s[i-1] - 'a' + 1;
Hash %= mod;
pre[i] = Hash;
}
for (int i=0; i<=s.size(); i++){
cout << i << " : " << pre[i] << endl;
}
cout << query(3, 3) << endl;
cout << query(4, 4) << endl;
cout << query(5, 5) << endl;
cout << query(3, 4) << endl;
cout << query(3, 5) << endl;
return 0;
}
Post Views (since April 2021) : 869