字符串哈希

fsjhhh Lv2

洛谷P3370

自然溢出字符串hash(单哈希hash)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const ULL base = 131;

ULL hash(std::string s) {
int len = s.size();
ULL ans = 0;
for (int i = 0; i < len; i++) {
ans = ans * base + (ULL)s[i];
}
return ans & 0x7fffffff;
}

void solve() {
std::map<ULL, int> mp;
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::string s;
std::cin >> s;
ULL z = hash(s);
mp[z] ++ ;
}
std::cout << mp.size() << "\n";
}

双模数hash

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
const ULL base = 131;
const ULL mod1 = 805306457, mod2 = 1610612741;

ULL hash_1(std::string s) {
int len = s.size();
ULL ans = 0;
for (int i = 0; i < len; i++) {
ans = (ans * base + (ULL)s[i]) % mod1;
}
return ans;
}

ULL hash_2(std::string s) {
int len = s.size();
ULL ans = 0;
for (int i = 0; i < len; i++) {
ans = (ans * base + (ULL)s[i]) % mod2;
}
return ans;
}

void solve() {
int n;
std::cin >> n;
std::map<std::pair<ULL, ULL>, int> mp;
for (int i = 0; i < n; i++) {
std::string s;
std::cin >> s;
ULL z1 = hash_1(s), z2 = hash_2(s);
mp[{z1, z2}] ++ ;
}
std::cout << mp.size() << "\n";
}

结构体哈希

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
const long long base = 131;
const long long mod1 = 805306457, mod2 = 1610612741;
using Hash = std::array<long long, 2>;

struct HASH {
int n;
std::string s;
std::vector<Hash> hash;
std::vector<Hash> p;

HASH() {}
HASH(std::string s) {
init(s);
}

void init(std::string a) {
this -> s = a;
n = s.size();
s = " " + s;
hash.assign(n + 1, {0, 0});
p.assign(n + 1, {0, 0});
for (int i = 1; i <= n; i++) {
hash[i][0] = (base * hash[i - 1][0] + (long long)s[i]) % mod1;
hash[i][1] = (base * hash[i - 1][1] + (long long)s[i]) % mod2;
}
p[0] = {1, 1};
for (int i = 1; i <= n; i++) {
p[i][0] = p[i - 1][0] * base % mod1;
p[i][1] = p[i - 1][1] * base % mod2;
}
}

Hash get(int l, int r) {
l += 1, r += 1;
Hash res;
res[0] = ((hash[r][0] - hash[l - 1][0] * p[r - l + 1][0] % mod1) % mod1 + mod1) % mod1;
res[1] = ((hash[r][1] - hash[l - 1][1] * p[r - l + 1][1] % mod2) % mod2 + mod2) % mod2;
return res;
}

};
  • 标题: 字符串哈希
  • 作者: fsjhhh
  • 创建于 : 2023-11-19 20:19:04
  • 更新于 : 2024-08-18 23:26:41
  • 链接: https://fsjhhh.github.io/2023/11/19/字符串哈希/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论