hash应用

关于HASH

这应该是经常使用的一个算法,因为其预处理后,优秀的$O(1)$处理出子串,并且$O(1)$比较,大快人心,而且写法简单,令人心情愉悦;

但是其空间复杂度较高,并且有玄学模数以及哈希冲突,以至于如果想hack,其实可以hack掉;

前置知识

关于进制,模数,hash就用到了重构进制,取模稀疏,所以哈希表又叫稀疏表;

入坑

hash很好理解,而且匹配非常方便,~~不容易写炸,对于萌新十分友好~~,

HASH查询

我们知道数字匹配复杂度为 $O(1)$ ,数字匹配速度快,而字符串却只能一个一个匹配, ~~这不公平~~ .那么我们考虑将字符串变成数字.

想一下数字有进制,那么我们定义一下字母的进制,不一定是26,我们可以随便取一个数,习惯性取质数;

但是数字太长,爆 $long$ $long$ 我们没办法存怎么办,我们考虑字符串很少,但是空间很大,我们考虑将数字安排入一个位置,其实这个位置是随机的,但是我们可以推出,这就够了;

那么我们可以模一个数字,将数字限制在一个范围之内,然后储存下来,而这个模数一般是一个质数,因为质数的特殊性质,可以造成更好地将数字稀疏;

模版

#define ll long long
const ll base=133;
const ll mod=19491001;
ll id(char s[]){
	int l=strlen(s);ll ol=0;
	for(int i=0;i<l;i++)
		ol=(ol*base+s[i]-'a'+1)%mod;
	return ol;
}

处理复杂度 $O(n)$ 然后开个数组储存即可;

HASH子串匹配

我们知道,如果每次都处理出一个串的子串,那么时间复杂度 $O(n^2)$ ,这是我们不能接受的,但是考虑一下我们存的是数字,数字有进制,那么一定可以通过加减操作得到其子串,那么,就简单很多了;

我们可以先预处理出 $HASH$ 前缀和,之后通过加减得到一段区间的子串;

但是直接开数组了话,有可能开不下,或者加大hash冲突的可能(即两个字符串hash值相同),那么我们可以考虑在不超时的情况下,加入一个map储存hash值,这样不需再担心空间问题,但是每次查询时间会多一个 $logn$ ,请谨慎使用;

例题

我不再直接附上模版,而是引入一个例题;

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

做法

我们可以二分枚举公共子串长度,因为公共子串长度一定是满足单调性质的.

那么我们选择枚举第一个串的子串,然后将其他串中相同长度的子串储存起来,那么就可以匹配了;

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 2007
#define ll long long
using namespace std;
const ll base=133;
const ll mod=998244353; 
map<int,bool>ha[6];
ll sum[6][maxn],ad[maxn];
int n,lim=maxn,len[6];
char c[6][maxn];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
	type_of_scan f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
template<typename top,typename... tops>
inline void scan(top &x,tops&... X){
	scan(x),scan(X...);
}

int id(int pos,int l,int r){
	return (sum[pos][r+1]-sum[pos][l]*ad[r-l+1]%mod+mod)%mod;
}

bool check(int l){
	for(int i=1;i<=n;i++) ha[i].clear();
	for(int i=2;i<=n;i++){
		for(int j=0;j+l-1<len[i];j++)
			ha[i][id(i,j,l+j-1)]=1;
	}
	for(int i=0;i+l-1<len[1];i++){
		int temp=id(1,i,i+l-1),cnt=n-1;
		for(int j=2;j<=n;j++){
			if(ha[j][temp]) cnt--;
		}
		if(!cnt) return 1;
	}
	return 0;
}

void init(){
	ad[0]=1;
	for(int i=1;i<=2001;i++) ad[i]=ad[i-1]*base%mod;
	for(int i=1;i<=n;i++){
		for(int j=0;j<len[i];j++){
			sum[i][j+1]=(sum[i][j]*base+(c[i][j]-'a'))%mod;
		}
	}
}

int main(){
	scan(n);
	for(int i=1;i<=n;i++)
		scanf("%s",c[i]),lim=min(len[i]=strlen(c[i]),lim);
	int l=0,r=lim;init();
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
}

关于HASH

前置知识

入坑

HASH查询

模版

HASH子串匹配

例题

做法

code

TO BE CONTINUED