[acm]hash学习笔记

hash学习

hash是一种比较常见的处理字符串的手法。在acm题目中,经常使用hash来处理字符串。比如判断一个子串在一个字符串中出现过几次。就可以使用hash来处理。

hash主要的方法就是把不同的字符串对应到不同的数字,之后通过数组来确定字符串是否出现过,从而减少检索字符串的时间。

常见的hash方法

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef unsigned long long ull;
ull base[maxn],has[maxn];
void init(){
base[0] = 1;
rep(i,1,maxn) base[i] = base[i-1] * 131;
scanf("%s",s);
int len = strlen(s);
has[len] = 0;
per(i,0,len) has[i] = has[i+1]*131 + (s[i]-'a'+1);
}
ull get_hash(int i,int L){
return has[i] - has[i+L]*base[L];
}

练习

hdoj4821 String

题目大意就是求$S$子串中,

  • 长为$M*L$
  • 其中每一段连续的$L$长度的子串都各不相同。

就是使用hash来做。但是我TLE了。因为暴力了每一段的hash值。

其实由于如果$S$的长度很长的话。其中很多段子段的hash值是被反复求的。所以我们在求完一段$M$个的字符串之后,就可以按照这个把第一段去除。之后选择后一段。这样重复下去。

Wa1:等于号想清楚了在判定。

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
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
typedef unsigned long long ull;
const int maxn = 1e5+10;
ull xp[maxn],Hash[maxn];
void init(){
xp[0] = 1;
rep(i,1,maxn) xp[i] = xp[i-1] * 175;
}
ull get_Hash(int i,int L){
return Hash[i] - Hash[i+L] * xp[L];
}
int n,m;
char s[maxn];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
init();
// m = length of L
while(~scanf("%d%d",&n,&m)){
scanf("%s",s);
int len = strlen(s);
Hash[len] = 0;
per(i,0,len){
Hash[i] = Hash[i+1]*175+(s[i]-'a'+1);
}
int ans = 0;
for(int i=0;i<m && i<=len-m*n;i++){
map<ull,int> mx;
for(int j=i;j<i+m*n;j+=m){
ull temp = get_Hash(j,m);
mx[temp] ++;
}
if(mx.size() == n) ans++;
for(int j = i+n*m;j+m<=len;j+=m){
ull temp = get_Hash(j-n*m,m);
mx[temp]--;
if(mx[temp] == 0) mx.erase(temp);
temp = get_Hash(j,m);
mx[temp]++;
if(mx.size() == n) ans++;
}
}
printf("%d\n",ans);
}
return 0;
}

hdoj4080 Stammering Aliens

题目大意是找到字符串$S$中,出现次数大于$m$次并且最长的字符串。

我是用hash做的,不过时间是4800ms,差点超时。用别人后缀数组+二分,200ms可以过。。

就酱吧。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 4e4+10;
ull base[maxn],has[maxn];
void init(){
base[0] = 1;
rep(i,1,maxn) base[i] = base[i-1] * 131;
}
ull get_hash(int i,int L){
return has[i] - has[i+L] * base[L];
}

int m,n;
char s[maxn];
int check(int len){
map<ull,int> mx;
int ans = -1;
rep(i,0,n-len+1) {
ull temp = get_hash(i,len);
mx[temp] ++;
if(mx[temp] >= m){
ans = i;
}
}
return ans;
}
int right_most = 0;
int res = 0;
void solve(int l,int r){
int mid;
while(l<=r){
mid = l+r>>1;
int temp = check(mid);
if(temp != -1){
l = mid + 1;
res = mid;
right_most = temp;
}else{
r = mid - 1;
}
}
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
init();
while(scanf("%d",&m) && m){
scanf("%s",s);
n = strlen(s);
has[n] = 0;
per(i,0,n) has[i] = has[i+1] * 131 + s[i] - 'a' + 1;
right_most = 0; res = 0;
solve(1,n+1);
if(res == 0){
puts("none");
}else{
printf("%d %d\n",res,right_most);
}
}

return 0;
}

reference:

https://blog.csdn.net/u012965373/article/details/38929637

https://blog.csdn.net/ck_boss/article/details/47066727