题解 P3370 【【模板】字符串哈希】
Hatsune_Miku
2017-05-09 08:17:37
然而这个题，单哈希也能过，数据应该加强。
事实上常用的哈希函数也就那么几个。编码效率和运行效果最好的大概就是BKDRHash算法了。
对于BKDRHash，如果有冲突就换一个种子就好了。可以有131,13131等各种各样奇怪的种子（都不保险，正统的解决方案是写个链表或者后移）。
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
char ch[10000];int n,cnt;
unsigned int a[10000];
inline unsigned int BKDRHash(char *str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while (*str)
hash = hash * seed + (*str++);
return (hash & 0x7FFFFFFF);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",ch);
a[i]=BKDRHash(ch);
}
sort(a,a+n);
for(int i=0;i<n;i++)
if(a[i]!=a[i+1])
cnt++;
printf("%d",cnt);
return 0;
}
```
蒟蒻渣渣代码。判重写的非常丑。
友情提示：对于Hash函数，建议加上inline提高效率，会有意想不到的效率提升（~1200ms->~200ms）
对于大数据，请善用scanf与printf。
就酱。