百度站长怎么做网站维护,哈尔滨网站推广,企业云平台管理系统,一键优化免费下载很久没遇到过hash的题了#xff0c;今天来重新温故一下 文章目录序言常用的几个字符串hash方法#xff1a;hash公式#xff08;自然溢出#xff09;讲解模板单hash讲解模板双hash讲解代码总结序言
你有没有想过#xff0c;字符串存储一大溜#xff0c;比较时又麻烦又折腾…很久没遇到过hash的题了今天来重新温故一下
文章目录序言常用的几个字符串hash方法hash公式自然溢出讲解模板单hash讲解模板双hash讲解代码总结序言
你有没有想过字符串存储一大溜比较时又麻烦又折腾我当年oi时就想要是能转化成整数就好了 诶字符串hash其实就是把一个字符串转化成整数 你也可以把hash的过程理解成加密但是不同字符串加密后的“密文”互不相同 说起来容易我们怎么才能做到不冲突不重复呢这里就开始讲解hash
常用的几个字符串hash方法
Ss1s2s3s4…sn idx(s[i]) s[i] - ‘a’
hash公式自然溢出
讲解
unsigned long long hash[N]; hash[i]hash[i-1]*p s[ i ] (自动取模) p为质数(常取31) unsigned long long的范围会自然一处相当于自动对264 取獏
模板 char s[10010];
ull hashs(char s[])
{int lenstrlen(s);ull base131;ull ans0;for (int i1;ilen;i)ansans*base(ull)s[i];return ans0x7fffffff;//舍弃符号位
}首位是符号位 0x7fffffff之后符号位固定为0代表正数后面保持不变可以理解成取正
单hash
讲解
hash [ i ] ( hash [ i - 1 ] * p idx ( s [ i ] ) ) % mod 其中p与mod均为质数 对了p与mod越大重复的概率越低
模板 char s[10010];
ull mod101;
ull hashs(char s[])
{int lenstrlen(s);ull base13;ull ans0;for (int i1;ilen;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 mod113;
ull mod217;
ull hash1(char s[])
{int lenstrlen(s);ull ans0;for (int i0;ilen;i)ans(ans*base(ull)s[i])%mod1;return ans;
}
ull hash2(char s[])
{int lenstrlen(s);ull ans0;for (int i0;ilen;i)ans(ans*base(ull)s[i])%mod2;return ans;
}总结
对于一个字符串我们可以预处理1~L的hash值这样通过O1的方法递推出来
