单hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define base 233
#define inf 1<<30
ull mod = inf;
//定义一个大数(最好是质数)作为模数，这里用的是1<<30
//定义一个base进制，这里是233
il ull hash(char s[]){
    ll ans = 0;
    ll len = strlen(s);
    for(ll i = 0; i < len; i++){
        ans = (base * ans + (ull)s[i]) % mod;
    }
    return ans;
    //枚举该字符串的每一位，与base相乘，转化为base进制，加(ull)是为了防止爆栈搞出一个负数，(ull)是无符号的，但其实加了一个ull是可以不用mod的，加个mod更保险
    //然而加了mod会很玄学，莫名比不加mod慢了300多ms
}

双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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
#define ll int
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define ull unsigned long long
using namespace std;
#define N 10001
#define base 233
ull mod1 = 212370440130137957ll;
ull mod2 = inf;

ll n;
char a[N];
struct node { ll x, y; }f[N];

inline ull hash1(char s[]) {
    ll ans = 0, len = strlen(s);
    for (ll i = 0; i < len; i++) {
        ans = (base * ans + (ull)s[i]) % mod1;
    }
    return ans;
}

inline ull hash2(char s[]) {
    ll ans = 0, len = strlen(s);
    for (ll i = 0; i < len; i++) {
        ans = (base * ans + (ull)s[i]) % mod2;
    }
    return ans;
}

bool cmp1(node a, node b) { return a.x < b.x; }
bool cmp2(node a, node b) { return a.y < b.y; }

int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        scanf("%s", a);
        f[i].x = hash1(a);
        f[i].y = hash2(a);
    }
    sort(f + 1, f + n + 1, cmp1); sort(f + 1, f + n + 1, cmp2);
    ll ans = 1;
    for (ll i = 1; i < n; i++) {
        if (f[i].x != f[i + 1].x || f[i].y != f[i + 1].y)ans++;
    }
    printf("%d\n", ans);
    return 0;
}