P3370 【模板】字符串哈希

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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 1510;
const int base = 261;
const int MOD = 23333;

int n, ans = 0;
char s[MAXn];
vector<string> hash[MOD + 2];

inline void insert() {
    int mo = 1;
    for (int i = 0; s[i]; i++)
        mo = (mo * 1ll * base + s[i]) % MOD;
    string s2 = s;
    for (int i = 0; i < hash[mo].size(); i++)
        if (hash[mo][i] == s2)
            return;
    hash[mo].push_back(s2);
    ans++;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%s", &s), insert();
    printf("%d\n", ans);
    return 0;
}