-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstringHash.cpp
More file actions
47 lines (40 loc) · 946 Bytes
/
stringHash.cpp
File metadata and controls
47 lines (40 loc) · 946 Bytes
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
const long long B = 100050007;
const long long M = 1000000009;
long long power(long long n, long long m)
{
if (m == 0) return 1;
long long x = power(n, m / 2);
if (!(m & 1)) return (x * x) % M;
else return (((x * x) % M) * n) % M;
}
long long h[MAX];
long long pB[MAX], invB[MAX];
void pInit() {
pB[0] = 1;
for (int i = 1; i < MAX; i++) {
pB[i] = (pB[i-1] * B) % M;
}
invB[MAX-1] = power(pB[MAX-1], M-2);
for (int i = MAX-2; i >= 0; i--) {
invB[i] = (invB[i+1] * B) % M;
}
}
void init(){
int n = s.size();
h[0] = s[0];
for (int i = 1; i < n; i++) {
h[i] = ((s[i] * pB[i]) % M + h[i-1]) % M;
}
}
ll concat(ll h1, ll h2, ll n){
ll ret = (h1 + (h2*pB[n])%M)%M;
return ret;
}
ll getsubH( int i, int j){
if(i > j)
return 0;
ll jh = h[j];
ll ih = (i > 0)? h[i-1]: 0;
ll subHash = ((jh + M - ih) * invB[i]) % M;
return subHash;
}