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

字符串哈希从入门到精通

一、基本概念

字符串哈希是将任意长度的字符串映射为固定长度的哈希值(通常为整数)的技术,核心目标是实现O(1)时间的子串快速比较和高效查询。其本质是通过数学运算将字符串转换为唯一性较高的数值,例如:

                ​​​​​​​        ​​​​​​​                        

其中P为基数(根据题目),M为大质数s[i]字符的ASCII值

二.一般哈希实现

一般哈希的实现有两种方式:

通俗的讲叫:

1.蹲茅坑法

2.拉拉链法

2.1蹲茅坑法

假设你现在要处理19与12(mod 7)

你会发现19与12 mod 7 都是5!

这应该怎么办?

你就可以想象成你要蹲茅坑,5号坑有人了!那你不是得去下一个坑吗!!!

如果5号有19,那么我们就把12入6号;

2.2拉拉链法

你把每个格想象成一个链表,把相同的存进链表里就行。

但是以上的都不重要……

三.字符串哈希

字符串哈希的原理其实很简单,就是把这个字符串看成一个多进制的数,然后将这个数化成十进制数的结果就是哈希的结果。(如同十进制的数字每一个都是唯一的,所以说哈希值不存在重复)

直接上代码!!!

for(int i=0;i<s1.size();i++){
	ans=(ans*128+s1[i])%998244353;
    //ans*128是将上一位数前移
    //最后一般都会取余一个大质数(1e9,998244353)
}

还有一个:

ll geth(int l,int r){
    return has[r]-has[l-1]*pw[r-l+1];
    //得到这个区间内的哈希值(类似前缀和)
    //qw[r-l+1]是为了对齐方便减
}

是不是很简单!!!

四.例题《查字典》

4.1题目

4.2思路

我们先把每个外语单词的哈希值算出来,然后m次输入,再把输入的哈希值算出来,最后遍历哈希数组,有这个哈希值就输出所对应的英文单词,没有就输出“eh”

4.3代码

#include<bits/stdc++.h>
using namespace std;
long long ans,has[1005],mod=1e9+7,n,m;
string s1[1005],s2[1005],s3;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
	for(int i=1;i<=n;i++){
	    cin>>s1[i]>>s2[i];
	    for(int j=0;j<s2[i].size();j++){
    		has[i]=has[i]*128+1ll*s2[i][j];
    	}
	}
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>s3;
		ans=0;
		for(int j=0;j<s3.size();j++){
    		ans=ans*128+1ll*s3[j];
    	}
    	bool flag=0;
    	for(int j=1;j<=n;j++){
    	    if(has[j]==ans){
    	        cout<<s1[j]<<"\n";
    	        flag=1;
    	    }
    	}
    	if(flag==0){
    	    cout<<"eh"<<"\n";
    	}
	}
	return 0;
}

加纳!!!!!!!


http://www.kler.cn/a/589913.html

相关文章:

  • VSCode + CMake
  • 系统架构设计师—案例分析—数据库篇—分布式缓存技术
  • 【C++标准库类型】深入理解vector类型(2):迭代器与算法
  • 做游戏的发展方向
  • Java泛型程序设计使用方法
  • 矩阵期望 E 的含义:概率
  • npm : 无法加载文件 C:\Program Files\nodejs\npm.ps1,因为在此系统上禁止运行脚本的处理方法
  • 【软件工程】04_面向对象需求分析方法
  • 【C++进阶一】STL和string
  • SAP HANA on AWS Amazon Web Services
  • 一个使用Python和相关深度学习库(如`PyTorch`)实现GCN(图卷积网络)与PPO(近端策略优化)强化学习模型结合的详细代码示例
  • 设计模式-对象创建
  • 【存储中间件】Redis核心技术与实战(四):Redis高并发高可用(Redis集群介绍与搭建)
  • springboot纯干货
  • RAGFlow部署与使用(开源本地知识库管理系统,包括kibana配置)
  • Linux驱动开发之中断处理
  • kafka详细介绍以及使用
  • Java语言前言
  • 基于ssm的电子病历系统(全套)
  • 标贝自动化数据标注平台推动AI数据训练革新