字符串哈希
字符串哈希是一种哈希函数
得到哈希值
自然溢出：进行加减乘时，多出的位直接去掉，相当于每次都对取模
得到整个字符串的哈希值：
得到任何子串的哈希值：
- 选择一个质数做进制数，设为base
- 得到base的各种次方，在自然溢出下用数组记录
- 得到每个位置的哈希
hash[i]=hash[i-1]*base+s[i]-'a'+1
- 字串s[l…r]的哈希值为
hash[r]-hash[l-1]*base^(r-l+1)
代码
整个字符串的哈希值：
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
| #include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int base = 1e9+7;
ll value(string s){
ll ans = s[0]-'a';
for (int i = 1;i<s.size();i++){
ans = ans*base+(s[i]-'a');
}
return ans;
}
void solve() {
int n;
vector<ll> hash_s;
cin >> n;
for(int i = 1;i<=n;i++){
string s;
cin >> s;
hash_s.push_back(value(s));
}
sort(hash_s.begin(),hash_s.end());
hash_s.erase(unique(hash_s.begin(), hash_s.end()), hash_s.end());
cout << hash_s.size();
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tomorin=1;
while (tomorin--) solve();
return 0;
}
|
子串哈希值：
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
| #include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int base = 1e9+7;
vector<int> pows(N);
vector<int> hash_t(N);
void value(string s){
pows[0]=1;
for (int i = 1;i<s.size();i++){
pows[i] = pows[i-1]*base;
}
hash_t[0] = s[0] -'a'+1;
for (int i = 1;i<s.size();i++){
hash_t[i] = hash_t[i-1]*base +s[i]-'a'+1;
}
}
ll hash_get(ll l, ll r){
ll ans = hash_t[r];
if (l>0){
ans-=hash_t[l-1]*pows[r-l+1];
}
return ans;
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
value(s);
cout << hash_get(2,3);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tomorin=1;
while (tomorin--) solve();
return 0;
}
|
