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查询

模版

HASH子串匹配

例题

做法

code

TO BE CONTINUED

最新文章

热门文章