题解 P3370 【【模板】字符串哈希】
teafrogsf
2017-08-23 15:54:29
### pb\_ds大法好
这里提供一个正儿八经的不用手写的哈希表——pb\_ds库里的hash\_table。
因为map内部排了序,所以会慢一些,而hash\_table就和手写的几乎差不多了。
当然在我的代码中,把getline换掉应该会更快一些。
**使用pb\_ds库的hash\_table需要包含两个头文件**~~,其实我觉得pb\_ds库最难的就是背头文件了~~
上代码。
```cpp
#include<cstdio>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define f(i,a,b) for(register int i=int(a);i<=int(b);++i)
using namespace std;
__gnu_pbds::cc_hash_table<string,int>ht;//或者gp_hash_table,貌似慢一点
int main()
{
int n,sum=0;
string s,instead;
scanf("%d",&n);getline(cin,instead);
f(i,1,n)
{
getline(cin,s);
if(!ht[s])ht[s]=1,++sum;
}
printf("%d\n",sum);
}
```