首页 > 其他分享 >二维Hash

二维Hash

时间:2024-09-02 16:48:22浏览次数:8  
标签:p2 p1 hash int long times 二维 Hash

前置知识:字符串hash

我们定义一个字符串s的hash值为:

\[\begin{aligned} \sum _ {i = 1} ^ n s[i] \times p1 ^ {(n-i)}\end{aligned} \]

其中n是字符串的长度,i从1~n(下标从1开始),p1是一个稍微大一点的质数

code:

	int p1=13331;
	unsigned long long h=0; 
	for(int i=1;i<=n;i++){
		h=h*p1+(s[i]-'a');
	} 

如果我们要知道字符串s区间[l,r]的hash值,我们要先求出s的每一个前缀字符串的hash值,令f[i]表示前i个字符组成的字符串的hash值,则

\(Hash([l,r])=f[r]-f[l-1] \times p ^ {(r-l+1)}\)

(可以把原字符串想象成一个p进制数来理解)

定义

  • 我们定义一个n行m列的矩阵s的hash值为

    $ \sum _{i=1}^n f[i] \times p2^{(n-i)}$

    f[i]是第i行的hash值,p2是一个不同于p1的质数

  • h[i][j]表示矩形s,前i行前j列组成的矩形的hash

于是可以得出求解h数组的代码:

void Hash1()
{
	for(int i=1;i<=n;i++)
	{
		unsigned long long tmp=0;
		for(int j=1;j<=m;j++)
		{
			tmp=tmp*p1+s[i][j]-'a';
			h[i][j]=tmp+h[i-1][j]*p2;
		}
	}
}

例题

acwing 矩阵

分析:

对于每一个询问,先处理出小矩阵的hash值,接着枚举大矩阵的每个点,如果能O(1)求出以这个点为右下角端点的大小为A\(\times\)B的矩阵的hash值,就可以O(1)判断了

那怎么求呢?
以n=6,m=8,i=5,j=6,a=2,b=3为例,下面每个格子代表一个字符,红色部分即为所求:(格子里的是那个字符的坐标)

用\(h[i][j]-h[i-a][j] \times (p2)^a\)就得到了蓝色部分

我们再减掉黄色部分其实就可以得到答案了

那黄色部分怎么求呢?

黄色部分其实就是\(h[i][j-b]-h[i-a][j-b] \times (p2)^a\)

但是在蓝色部分-黄色部分的时候黄色部分整体要乘上\(p1^b\)

所以答案就是

\(h[i][j] - h[i-a][j] \times (p2)^a - ( h[i][j-b] - h[i-a][j-b] \times (p2)^a) \times (p1)^b\)

\(= h[i][j] - h[i-a][j] \times (p2)^a - h[i][j-b] \times (p1)^b + h[i-a][j-b] \times (p2)^a \times (p1)^b\)

其实和前缀和是一样的

最后附上完整代码

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N=1e5+5;
const unsigned long long p1=100003,p2=133331;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,a,b,q;
unsigned long long m1[1005],m2[1005];
char s[1005][1005]; 
unsigned long long h[1005][1005];
unsigned long long g[1005][1005];
void Hash1()
{
	for(int i=1;i<=n;i++)
	{
		unsigned long long tmp=0;
		for(int j=1;j<=m;j++)
		{
			tmp=tmp*p1+s[i][j]-'0';
			h[i][j]=tmp+h[i-1][j]*p2;
		}
	}
}
map<unsigned long long,bool> mp;
char t[1005][1005];
unsigned long long Hash2()
{
	unsigned long long hsh=0;
	for(int i=1;i<=a;i++)
	{
		unsigned long long tmp=0;
		for(int j=1;j<=b;j++)
		{
			tmp=tmp*p1+t[i][j]-'0';
		}
		hsh=hsh*p2+tmp;
	}
	return hsh;
}
signed main()
{
	m1[0]=m2[0]=1;
	for(int i=1;i<=1000;i++) m1[i]=m1[i-1]*p1,m2[i]=m2[i-1]*p2;
	n=read(),m=read(),a=read(),b=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
		}
	}
	Hash1();
	for(int i=a;i<=n;i++)
	{
		for(int j=b;j<=m;j++)
		{
			g[i][j]=h[i][j]-h[i][j-b]*m1[b]-h[i-a][j]*m2[a]+h[i-a][j-b]*m1[b]*m2[a];
			mp[g[i][j]]=1; 
		}
	}
	q=read();
	while(q--)
	{
		for(int i=1;i<=a;i++)
		{
			for(int j=1;j<=b;j++)
			{
				cin>>t[i][j];
			}
		}
		unsigned long long hsh=Hash2();
		if(mp[hsh]) cout<<1<<endl;
		else cout<<0<<endl;
	}
	return 0;
}

标签:p2,p1,hash,int,long,times,二维,Hash
From: https://www.cnblogs.com/FloatingLife/p/18392985

相关文章

  • java~重写hashcode和equals
    单字段和多字段重写hashcode在Java中,重写hashCode方法的场景通常与对象的哈希值计算有关,特别是在使用哈希表(如HashMap,HashSet等)时。下面是你提供的两种hashCode实现的具体使用场景分析:1.第一种实现@Overridepublicbooleanequals(Objecto){if(this==o)......
  • php使用QRcode类生成二维码
    参考:https://www.cnblogs.com/txw1958/p/phpqrcode.html1.下载到最新版本:http://sourceforge.net/projects/phpqrcode/。解压后,只需要使用phpqrcode.php文件即可,解压后目录如下:  2.测试代码:publicfunctionqrcode($url){require_onceFCPATH.'application/third_......
  • 题解:AT_abc257_d [ABC257D] Jumping Takahashi 2
    [ABC257D]JumpingTakahashi2博客食用更佳:Myblog。大体思路这题是一道二分题,因为\(S\)越大,就越容易满足题目要求,\(S\)越小,就越难满足题目要求,符合二分的特点。下面先贴上二分代码。LLl=0,r=1e10;while(l<r){intmid=l+r>>1;if(check(mid))......
  • equals ,hashcode ,== ,三者之间的关系与区别
    为什么要重写equals和hashcode        在Java中,重写equals方法和hashCode方法是为了确保对象在逻辑上相等时,它们在集合(如HashMap、HashSet)中的行为也是一致的。以下是详细解释:为什么要重写 equals 方法默认行为:默认情况下,Object类的equals方法比较的是两个对......
  • 哈希表hashtable课堂笔记
    /*哈希表,表示键/值对的集合,这些键/值对根据键的哈希代码进行组织。它的每个元素都是一个存储在DictionaryEntry对象中的键/值对。键不能为空引用,但值可以。哈希表的构造函数有多种,这里介绍两种最常用的。*///(1)使用默认的初始容量、加载因子、哈希代码提供程序和比......
  • Hash哈希学习笔记
    概念:通过一个hash函数建立值与存储地址的关系原则:开小数组+冲突解决冲突越少,用时越少;可通过调整余数或优质的hash算法尽量使hash值分散,减少碰撞hash算法的构成:hash函数的初始化构造hash函数:典型的函数包括除余法H......
  • 一文说透 String 的 HashCode
    首先需要明确版本,不同版本的实现是不同的。JDK1.8以前底层的实现是char[]。publicinthashCode(){inth=hash;if(h==0&&value.length>0){charval[]=value;for(inti=0;i<value.length;i++){h=31*......
  • HashMap 的长度为什么是2的幂次方?
    一、均匀分布哈希值当HashMap的长度是2的幂次方时,通过hashCode()计算出哈希值后,再与(length-1)进行与操作(例如index=hashCode()&(table.length-1)),可以使得哈希值更加均匀地分布在数组的下标范围内。假设哈希值是均匀分布的,那么与操作可以充分利用哈希值的各个位,......
  • 二维数组传参要点
    最近在写代码的时候又一次遇到了需要二维数组传参的操作,捣鼓了半天,总是会指针有问题,上网上查阅了相关资料后,虽然弄懂了,但是后面还是把二维改成一维了。但是呢?还是把相关的学习记录整理下来,以防后续还是需要用上。 这里主要以如何声明函数,如何调用函数,在函数中如何使用来讲解。形......
  • 在图片上加二维码,并且添加文字
    //设置响应头,输出图片//header('Content-Type:image/png');$domain=$this->request->domain();//$public=public_path();//echo$domain.'/mask.png';die;//$res=file_get_contents("./ba......