【字符串】字符串哈希
2021/8/10 23:38:19
本文主要是介绍【字符串】字符串哈希,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 字符串哈希
- 哈希
- 字符串哈希
- 字符串的哈希冲突:
- 字符串哈希的思想
- 字符串哈希的基本运算
- AcWing 138. 兔子与兔子
字符串哈希
哈希
哈希就是将所要处理的数据转化成数字,且这个数字能唯一地去对应上这个数据,若这个数字对应上了多个数字,则称作哈希冲突。比如\(K_{1}!=K_{2}\),但\(hash(K_{1})=hash({K_{2}})\)
字符串哈希
概念:字符串哈希是指将一个任意长度的字符串映射成一个非负整数,并且冲突的概率几乎为0.
字符串的哈希冲突:
冲突:两个字符串不相等,但是他们的p进制数相同
字符串哈希的思想
将字符串看成一连串的数字,字符串里的每一位看成在某一个特定位置上的单独的数字,并对这个数字赋予一定的权值,设为P(也用P来指说字符串可以看成是一个P进制数),这时候我们可以将由代表这个字符串的P进制数转化成十进制数, 并向一个固定的数M取余(M代表的是哈希值的范围).
- P一般取131或者13331,如果题目的字符串仅有小写字母,可以考虑取26.
- M可以设置成是2的64次方(只需unsigned long long),一方面,超出上界(溢出)后,数值会自动从0开始计算,这种天然的取余操作相比于再去使用mod取余操作会更高效.(面向一些大质数取余,比如1E9,能减少哈希冲突的概率(数论的知识,还不太懂)),另一方面,unsigned long long 具有数据范围大,能容纳的哈希值更多.
例子: 我们将a~z一一与1到26对应
\(hash("abcb")=a*P^{3}+b*P^{2}+c*P^{1}+b*P^{0}\)
字符串哈希的基本运算
- 已知某一字符串的哈希值,在其字符串的尾巴继续添置一个字母,求新组成的字符串的哈希值.
\(hash("abcb"+'d') =hash("abcbd")=(a*P^{4}+b*P^{3}+c*P^{2}+b*P^{1}+d=hash("abcb")*P+d)\%\space mod\)
-
进而我们有,已知字符串S和字符串T的哈希值,求S+T的哈希值
\[H(S+T)=(H(S)\times P^{len-of-T}+H(T))\% \space mod$$ \]\[H(T) =(H(S+T)-H(S)*P^{len-of-T})\%\space mod$$ \]
AcWing 138. 兔子与兔子
#include <bits/stdc++.h> #define MEM(a,x) memset(a,x,sizeof(a)) #define W(a) while(a) #define gcd(a,b) __gcd(a,b) #define pi acos(-1.0) #define PII pair<int,int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define ull unsigned long long #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define MAX 1000005 #define MOD 1000000007 #define INF 0x3f3f3f3f #define lowbit(x) (x&-x) using namespace std; int n,m; const int P=131,N = 1E6+10; ull h[N],mul[N]; void pre_work(string s) { MEM(h,0); mul[0]=1; repd(i,1,s.length()) { h[i]=h[i-1]*P+(s[i-1]-'a'+1); mul[i]=mul[i-1]*P; } } int main() { string dna; int t; cin>>dna>>t; pre_work(dna); while(t--) { int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2; if( (h[r1]-h[l1-1]*mul[r1-l1+1]) == (h[r2]-h[l2-1]*mul[r2-l2+1]) ) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
这篇关于【字符串】字符串哈希的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南