模板

单哈希

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const ull mod=212370440130137957ll;
ull base=131,a[10010];
int n,sum=1;
char s[10010];
ull hash(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod;
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        a[i]=hash(s);
    }
    sort(a+1,a+1+n);
    for(int i=2;i<=n;i++)
        if(a[i]!=a[i-1])
            sum++;
    printf("%d
",sum);
    return 0;
}

双哈希

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const ull mod1=19260817;
const ull mod2=19660813;
struct data{
    ull x,y;
}a[10010];
ull base=131;
int n,sum=1;
char s[10010];
ull hash1(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}
ull hash2(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}
bool cmp(data a,data b){
    return a.x<b.x;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        a[i].x=hash1(s);
        a[i].y=hash2(s);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=2;i<=n;i++)
        if(a[i].x!=a[i-1].x || a[i].y!=a[i-1].y)
            sum++;
    printf("%d
",sum);
    return 0;
}

例1：「LibreOJ NOIP Round #1」DNA 序列

很水的题，搞个map 和hash前缀和即可

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int base=131;
const int N=5e6+10;
char s[N];
int k;
ull has[N],ak;
map<ull,int>cnt;
int mx=0;
int main(){
    scanf("%s",s+1);
    scanf("%d",&k);
    int len=strlen(s+1);
    ak=1;
    for(int i=1;i<=k;i++)
        ak=ak*base;
    has[0]=0;
    for(int i=1;i<=len;i++)
        has[i]=has[i-1]*base+s[i];
    for(int i=1;i<=len-k+1;i++)
        mx=max(mx,++cnt[has[i+k-1]-has[i-1]*ak]);
    printf("%d
",mx);
    return 0;
}

例2：企鹅QQ

枚举哪一位不同，hash 除了 i 这一位的前缀和后缀

然后sort比较即可

#include <iostream>
#include <cstdio>
#include <algorithm>
const int N=3e4+5;
const int M=205;
using namespace std;
typedef unsigned long long ull;
inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
	return x;
}
int n,l,s,sum,ans;
char ch[M];
ull hs[N],hs1[N][M],hs2[N][M];
int base1=131,base2=137;
void init(int x){
	for(int i=1;i<=l;i++)
		hs1[x][i]=hs1[x][i-1]*base1+ch[i];
	for(int i=l;i>=1;i--)
		hs2[x][i]=hs2[x][i+1]*base2+ch[i];
}
int main(){
	n=read();l=read();s=read();
	for(int i=1;i<=n;i++){
		scanf("%s",ch+1);
		init(i);
	}
	for(int i=1;i<=l;i++){//枚举哪一位不同
		sum=1;
		for(int j=1;j<=n;j++)
			hs[j]=hs1[j][i-1]*233+hs2[j][i+1]*211;
		sort(hs+1,hs+1+n);
		for(int j=2;j<=n;j++)
			if(hs[j]==hs[j-1])
				ans+=sum,sum++;
			else sum=1;
	}
	printf("%d",ans);
	return 0;
}

例3：Stammering Aliens

Description

在一个字符串中求出现次数大于等于n的最长子串

Solution

二分子串长度，hash 然后存进map 里

#include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const ull mod=19260817;
ull base=131,a[40010];
int n,len,ans=-1;
char s[40010];
ull has[40010];
bool check(int x){
    map<int,int>mp;
    ull res;
    for(int i=1;i+x-1<=len;i++){
        res=has[i+x-1]-has[i-1]*a[x];
        if(++mp[res]>=n) return 1;
    }
    return 0;
}
int get(int x){
    map<int,int>mp;
    ull res;
    int pos=-1;
    for(int i=1;i+x-1<=len;i++){
        res=has[i+x-1]-has[i-1]*a[x];
        if(++mp[res]>=n) pos=i;
    }
    return pos-1;
}
int main(){
    while(~scanf("%d",&n)){
        if(!n) return 0;
        scanf("%s",s+1);
        len=strlen(s+1);
        has[0]=0;a[0]=1;
        for(int i=1;i<=len;i++){
            has[i]=has[i-1]*base+s[i];
            a[i]=a[i-1]*base;
        }
        int l=1,r=len+1;
        ans=-1;
        //二分长度
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        if(ans<=-1) puts("none");
        else printf("%d %d
",ans,get(ans));
    }
}

例4：Hash Killer I

神奇构造题

https://www.cnblogs.com/sahdsg/p/10849807.html

例5：二维哈希

比较像二维前缀和

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int base1=131;
const int base2=233;
const int N=1005;
char s[N],c[105][105];
int n,m,a,b,q;
ull has[N][N],ak1=1,ak2=1;
map<ull,int>cnt;
int mx=0;
int main(){
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            has[i][j]=has[i][j-1]*base1+s[j];
    }
    for(int i=1;i<=n;i++)   
        for(int j=1;j<=m;j++)
            has[i][j]+=has[i-1][j]*base2;
    for(int i=1;i<=b;i++) ak1=ak1*base1;
    for(int i=1;i<=a;i++) ak2=ak2*base2;
    for(int i=a;i<=n;i++)
        for(int j=b;j<=m;j++)
            cnt[has[i][j]-ak2*has[i-a][j]-ak1*has[i][j-b]+has[i-a][j-b]*ak1*ak2]=1;
    scanf("%d",&q);
    while(q--){
        ull res=0,ans=0;
        for(int i=1;i<=a;res=0,i++){
            scanf("%s",c[i]+1);
            for(int j=1;j<=b;j++)
                res=res*base1+c[i][j];
            ans=ans*base2+res;
        }
        if(cnt.count(ans)) printf("1
");
        else printf("0
");
    }
    return 0;
}

哈希表

例题：

不重复数字

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N=5e5+15;
const int P=100003;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
struct HASH{
	int nxt[N],hd[P+100],val[N],tot,to[N];
	inline void ins(int v) {
		int x=(v%P+P)%P;
		for(int i=hd[x];i;i=nxt[i]) {
			if(to[i]==v) {
				++val[i];return;
			}
		}
		to[++tot]=v;val[tot]=1;nxt[tot]=hd[x];hd[x]=tot;
	}
	inline int query(int v) {
		int x=(v%P+P)%P;
		for(int i=hd[x];i;i=nxt[i]) 
			if(to[i]==v) return val[i];
		return 0;
	}
	inline void clear() {
//		for(int i=0;i<=tot;i++) hd[i]=0;
		memset(hd,0,sizeof(hd));
		tot=0;
	}
}H;
int n,a[N];
int main() {
	int T=read();
	while(T--) {
		H.clear();
		n=read();
		for(int i=1;i<=n;i++) {
			a[i]=read();
			if(H.query(a[i])) continue;
			H.ins(a[i]);
			printf("%d ",a[i]);
		}
		puts("");
	}
	return 0;
}

CF776C Molly's Chemicals

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll inf=1e15;
const int P = 100003;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
int n,k;
ll a[N],mi[65];
struct HashTable {
	int nxt[N],val[N],hd[N],tot;
	ll to[N];//hash 
	inline void ins(ll v) {
		int x=v%P;
		if(x<0) x+=P;
		for(int i=hd[x];i;i=nxt[i]) {
			ll y=to[i];
			if(y==v) {++val[i];return;}
		}
		to[++tot]=v;val[tot]=1;nxt[tot]=hd[x];hd[x]=tot;
	}
	inline int query(ll v) {
		int x=v%P;
		if(x<0) x+=P;
		for(int i=hd[x];i;i=nxt[i]) {
			ll y=to[i];
			if(y==v) return val[i];
		}
		return 0;
	}
	inline void clear() {
		memset(hd,0,sizeof(hd));
		tot=0;
	}
}H;
int main() {
	H.clear();
	n=read();k=read();
	int len=0;
	if(k==1) {
		mi[0]=1;len=1;
	} else if(k==-1) {
		mi[0]=1;mi[1]=-1;
		len=2;
	} else {
		ll x=1;
		while(-inf<=x&&x<=inf) 
			mi[len++]=x,x*=k;
	}
	H.ins(0);
	ll ans=0,sum=0;
	for(int i=1;i<=n;i++) {
		int x=read();sum+=x;
		for(int j=0;j<len;j++) 
			ans+=H.query(sum-mi[j]);
		H.ins(sum);
	}
	printf("%lld
",ans);
	return 0;
}