hash

hash公式（自然溢出）

讲解

unsigned long long hash[N];
hash[i]=hash[i-1]*p + s[ i ] (自动取模)
p为质数(常取31)

模板

char s[10010];
ull hashs(char s[])
{
int len=strlen(s);
ull base=131;
ull ans=0;
for (int i=1;i<=len;i++)
ans=ans*base+(ull)s[i];
return ans&0x7fffffff;//舍弃符号位
}

单hash

讲解

hash [ i ] = ( hash [ i - 1 ] * p + idx ( s [ i ] ) ) % mod
其中p与mod均为质数
对了，p与mod越大，重复的概率越低

模板

char s[10010];
ull mod=101;
ull hashs(char s[])
{
int len=strlen(s);
ull base=13;
ull ans=0;
for (int i=1;i<=len;i++)
ans=(ans*base+(ull)s[i])%mod;
return ans;
}

双hash

讲解

如果单hash你不放心，可以用双hash，更保险
将一个字符串hash两次，生成一个二元组，来代表原字符串，两个都比配才可以（相当于两把锁）
hash1[i]=(hash1[i−1]) ∗ p + idx(s[i]) % mod1
hash2[i]=(hash2[i−1])∗p + idx (s[i]) % mod2
pair< hash1 , hash2 > 表示一个字符串！

代码

char s[100];
ull mod1=13;
ull mod2=17;
ull hash1(char s[])
{
int len=strlen(s);
ull ans=0;
for (int i=0;i ans=(ansbase+(ull)s[i])%mod1;
return ans;
}
ull hash2(char s[])
{
int len=strlen(s);
ull ans=0;
for (int i=0;i ans=(ansbase+(ull)s[i])%mod2;
return ans;
}