字符串哈希
在 初学数据结构:哈希表的运用 — POJ 3349 Snowflake Snow Snowflakes 一文中，我们曾提及哈希表的概念。那么，什么是字符串哈希呢？
字符串哈希可以理解为一个P进制的数字，其哈希函数如下
H(i)=( H(i-1)*p+a(i) )%mod
i表示从1 – i
i-1表示从1 – i-1
a(i) 表示这个字符的值（通常取acill码）
p p进制数 mod 取模防止爆炸
仔细一看是个什么？？？进制转换！
经过这个函数基本上每个字符串都会对应一个整数
是不是有点像 康拓展开？ 实际上康拓展开也是一种设计的十分好的哈希可是我们依然会发现，得出来的值还是有一定几率重的,这个状况就叫做
哈希碰撞
一个哈希函数产生碰撞的可能性越低，我们就说这个哈希函数设计的越好
那么如何使自己的字符串哈希函数尽可能的变好呢?
如果mod与p是大质数,那么碰撞可能性会很低Qwq
但是这样依然有可能重复，所以我们一般用两个哈希函数，只有两个值相等时才判等
【模板】字符串哈希
明白了概念就来到模板题目把
题目
题意真的是水到了一个境界，所以我们直接上代码吧qwq
代码
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int p=19260817,mod=1000007,temp,temp2,cnt=0;
int p2=99983,mod2=10000007;
// 双哈希
char a[1600];//读入用
long long hash_tmp[1600],hash_tmp2[1600]// 计算哈希;
bool hash[1100000],hash2[11000000];// 哈希表
long long H(){//第一个哈希函数
int len=strlen(a+1);
for(int i=1;i<=len;i++){
hash_tmp[i]=(hash_tmp[i-1]*p+a[i])%mod;
}
return hash_tmp[len];
}
long long H2(){//第二个哈希函数
int len=strlen(a+1);
for(int i=1;i<=len;i++){
hash_tmp2[i]=(hash_tmp2[i-1]*p2+a[i])%mod2;
}
return hash_tmp2[len];
}
int main(){// 读入
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a+1);
temp=H();
temp2=H2();
if((!hash[temp])||(!hash2[temp2])){// 有任意一个没有出现过都表示这个字符串没有出现过
hash[temp]=true;
hash2[temp2]=true;
cnt++;
}
}
printf("%d",cnt);
}