哈希

2018-10-24

字数统计: 555字 | 阅读时长: 3min

哈希模板

typedef long long ll;
inline ll gethash(int *a)//a为你要哈希的数组（类型可以为char int） 
{
	ll rt=0;
	for(register int i=0;i<a.size();i++)
	{
		rt=(rt+a[i])*p%mod;//p为字符集大小，mod为模数； 
	}
	return rt; 
}

字符串哈希

#include<bits/stdc++.h>
const int p = 223;
const int mod =1e9+7;
using namespace std;
int n,ans;
int hash[10010];
int gethash(char *s)
{
    int len=strlen(s);
    int h[2000];
    for(int i=1;i<len;i++)
    {
        h[i]=(h[i-1]*p+s[i])%mod;
    }
    return h[len-1];
}
int main()
{
    scanf("%d",&n);
    char s[2000];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        hash[i]=gethash(s);
    }
    sort(hash+1,hash+1+n);
    for(int i=1;i<=n;i++)
    {
        if(hash[i-1]!=hash[i]) ans++;
    }
    printf("%d",ans);
    return 0; 
}

模板题比较水，单哈希即可通过。

具体题解我认为题解第一篇挺详细的，我就不再多说了了。

P2843 暗杀

#include<bits/stdc++.h>
using namespace std;
const long long mod = 1000000000039;
const long long  p = 200003;
typedef long long ll;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

int n,k;
int have[100100][35],sum[100100][35],c[100100][35];
long long hash1[100100],hash2[100100];
int ans;
map<ll,int> vis1,vis2;

inline void gethash(int i)
{
	for(register int j=1;j<=k;j++)
	{
		hash1[i]=((hash1[i]+sum[i][j]-sum[i][1])*p+mod)%mod;
	}
}

int main()
{
//	freopen("2.in","r",stdin);
	read(n);
	read(k);
	for(register int i=1,a;i<=n;i++)
	{
		read(a);
		for(register int j=0;j<k;j++)
        sum[i][j+1]=sum[i-1][j+1]+((a>>j)&1);
	}

	for(register int i=1;i<=n;i++) gethash(i);
	
	for(register int i=1;i<=n;i++)
	{
		if(hash1[i]==0) ans=max(ans,i);
		if(vis1[hash1[i]]) 
		{
//			if(vis1[hash1[i]]==vis2[hash2[i]])
			ans=max(ans,i-vis1[hash1[i]]);
//			else ans=max(ans,i-vis2[hash2[i]]);
		}
		if(!vis1[hash1[i]]&&hash1[i]!=0) vis1[hash1[i]]=i;
//		if(!vis2[hash2[i]]&&hash2[i]!=0) vis2[hash2[i]]=i;&&vis2[hash2[i]]
	}
	printf("%d\n",ans);
	return 0;
}

注意：
这道题的字符集大小非常大，需要开到2e5 !

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/2e3b1176.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！