字符串hash

 1 #include<iostream>
 2 #include<cstring> 
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 typedef unsigned long long ull;
 8 
 9 const int k1 = 233,p = 1e7+7;
10 const int k2 = 23333;
11 
12 int hash1[p],hash2[p];
13 int n,ans = 0,len;
14 char s[2000];
15 ull val1,val2;
16 
17 int main(){
18     cin >> n;
19     for(int i = 1;i <= n;i++){
20         cin >> s;
21         val1 = val2 = 0;
22         len = strlen(s);
23         for(int i = 0;i < len;i++)val1 = val1*k1 + s[i],val2 = val2*k2 + s[i];
24         if(hash1[val1%p]&&hash2[val2%p])continue;
25         hash1[val1%p] = hash2[val2%p] = 1;
26         ans++;
27     }
28     cout << ans << endl;
29 return 0;
30 }