【字符串】字符串哈希

字符串哈希

字符串哈希是一种哈希函数

得到哈希值

自然溢出：进行加减乘时，多出的位直接去掉，相当于每次都对\(2^{64}\)取模

得到整个字符串的哈希值：

• 选择一个质数做进制数，设为base

• 将字符串转化为base进制的数字并让其自然溢出

  转化code：ans = ans*base+v(s[i]);

• 让每一位的值从1开始，得到一个longlong数字代表字符串

• 利用数字比较代替字符串比较

得到任何子串的哈希值：

• 选择一个质数做进制数，设为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;
  //cin >> tomorin;
  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;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}