当前位置: 首页 > news >正文

字符串Hash

我们经常会遇到需要比较字符串大小的情况,普通的方法是使用一个for循环来进行比较,这样时间复杂度是\(O(n)\)的,非常慢

但是相比较之下数字比较就很快,那我们可以把字符串转换为数字进行比较

所以进入正题

进制Hash

有一个字符串abc

我们知道每一个字符使用ASCII码存储的

我们还知道一种东西叫做进制

我们可以把一个字符串看作是一个B进制的数

那么,我们把这个“数”转十进制会得到一个值,我们叫做Hash值

伪代码:

for(int i=1;i<=len;i++){ans+=s[i]*power;power*=B;
}

但这样还是要跑O(n)啊

我们可以考虑预处理,类似O(n)预处理,O(1)查询的模式

预处理:

power[0]=1;
for(int i=1;i<=len;i++){power[i]=power[i-1]*B;
}
for(int i=1;i<=len;i++){val[i]=val[i-1]*B+s[i];
}

那么我们进一步发现,可以·得到一个区间的Hash值:

int get_hash(int l,int r){return val[r]-val[l-1]*pw[r-l+1];
}

分析过程到时候补上

P3370

这里我们为了避免哈希冲突,可以考虑双哈希

如果两个哈希值都有过的话大概就是已经出现过了,其他情况就是没出现过

#include<bits/stdc++.h>
#define int unsigned long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18,B=13331,b=13131;
int n;
int t1[maxn],t2[maxn];
int get_hash1(string s){int res=1;int sum=0;for(int i=0;i<s.size();i++){sum+=s[i]*res;res*=B;}return sum;
}
int get_hash2(string s){int res=1;int sum=0;for(int i=0;i<s.size();i++){sum+=s[i]*res;res*=b;}return sum;
}
signed main(){cin>>n;int ans=0;for(int i=1;i<=n;i++){string s;cin>>s;int x=get_hash1(s);int y=get_hash2(s);if(t1[x]&&t2[y]){continue;}ans++;t1[x]++;t2[y]++;}cout<<ans<<endl;return 0;
}

P10468

区间Hash值模板题

#include<bits/stdc++.h>
#define int unsigned long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,mod=1e9+7,inf=1e18,B=13131;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n;
string s;
int val[maxn],pw[maxn];
int get_hash(int l,int r){return val[r]-val[l-1]*pw[r-l+1];
}
signed main(){cin>>s;int len=s.size();s='#'+s;pw[0]=1;for(int i=1;i<=len;i++){val[i]=val[i-1]*B+s[i];pw[i]=pw[i-1]*B;}int q;cin>>q;while(q--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(get_hash(l1,r1)==get_hash(l2,r2)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return 0;
}
http://www.hskmm.com/?act=detail&tid=23798

相关文章:

  • 详细介绍:代码世界的“数字刑侦”:深入解析代码审计实战
  • 三霍尔BLDC如何测量Hall同步角度(需要示波器)
  • QBXT2025S刷题 Day2
  • PyCharm中搭建PyTorch和YOLOv10开发环境 - 实践
  • 基于PCIe(XDMA)的多路(1-32路)信号采集与回放子系统, 多路视频、AD、光纤等信号,支持PR over PCIe
  • Spring事务管理:@Transactional注解
  • AI元人文的未来:软硬件协同发展研究报告——声明Ai研究
  • 个人主页网址
  • 10.3考试t3(similarity)solution
  • 安卓渗透测试流
  • 日志|寻找旋转排序数组中的最小值|寻找两个正序数组的中位数|二分查找
  • 有关三角剖分的性质
  • 西门子通信-自制示意
  • Vue之刷新页面会触发的生命周期函数
  • 傅里叶的一生
  • Dos命令学习(新手)
  • 吴恩达深度学习课程一:神经网络和深度学习 第一周:深度学习简介
  • 实用指南:AI Agent开发平台如何设计?核心架构与工作流实战案例详解
  • Numercial result of HAA-DRSM
  • 防重复提交的实现
  • Day25错误(error)与异常(exception)的简单认识
  • 算法课第一次作业
  • 1. 对拍板子
  • Luogu P14122 [SCCPC 2021] Direction Setting题解 最小费用流
  • MySQL_基础
  • 5 qoj14553 序列与整数对 题解
  • AT_arc064_d [ARC064F] Rotated Palindromes
  • vscode代码块格式转换器
  • 二分模板
  • 如何控制事务?