登录
← 返回首页 | 代码片段 › 6 字符串 › 6.4 字符串Hash › 字符串Hash / 搜索
JSON MD

6.4 字符串Hash

Snowflake Snow Snowflakes 最小表示法+Hash
44 行
CPP JSON
【Snowflake Snow Snowflakes(最小表示法+Hash)】 字符串哈希(String Hashing)模板,将字符串映射为整数便于快速比较。 核心函数: int sakura(int a[]) — 后缀数组 uLL Hash(int a[],int st) — 哈希计算 uLL find(int a[]) — 查找(并查集寻根/二分查找) 适用场景:字符串匹配、回文检测、子串统计、字典树检索
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#include<map>
#define R register int
#define uLL long long
int n,t,p=13333331,re,A[13];
std::map<uLL,int>pan;
inline int sakura(int a[]){
    R i=1,j=2,k;
    while(i<=6&&j<=6){
        k=0;
        while(k<6&&a[i+k]==a[j+k])++k;
        if(k==6)break;
        if(a[i+k]>a[j+k]){i+=k+1;if(i==j)++i;}
        else{j+=k+1;if(i==j)++j;}
    }
    return i<j?i:j;
}
inline uLL Hash(int a[],int st){
    R i=0;uLL x=0;
    for(;i<6;++i)x=x*p+(uLL)a[st+i];
    return x;
}
inline uLL find(int a[]){
    R x,y,i=1,k=0,b[13];
    for(;i<=6;i++)b[i]=a[7-i];
    for(i=1;i<=6;i++)a[i+6]=a[i],b[i+6]=b[i];
	x=sakura(a),y=sakura(b);
    for(i=0;i<6;i++)
		if(a[x+i]<b[y+i])return Hash(a,x);
		else if(a[x+i]>b[y+i])return Hash(b,y);
    return Hash(a,x);
}
int main(){
    scanf("%d",&n);R i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=6;j++)scanf("%d",&A[j]);
        uLL re=find(A);
        if(pan[re]){printf("Twin snowflakes found.");return 0;}
    	pan[re]=1;
	}
    printf("No two snowflakes are alike.");
}
字符串Hash表 兔子与兔子
20 行
CPP JSON
【字符串Hash表(兔子与兔子)】 字符串哈希(String Hashing)模板,将字符串映射为整数便于快速比较。 核心函数: LL Hash(int l,int r) — 哈希计算 关键配置: N=1e6+5 适用场景:字符串匹配、回文检测、子串统计、字典树检索
C++ 19 行 CPP
#include<iostream>
#include<string>
#include<cstdio>
#define LL long long
using namespace std;
const int N=1e6+5;
int l1,r1,l2,r2,n,m,i,p=27;
LL f[N],mi[N];string a;
inline LL Hash(int l,int r){return f[r]-f[l-1]*mi[r-l+1];}
int main(){
    cin>>a;n=a.size();a='$'+a;mi[0]=1;
    for(i=1;i<=n;i++)f[i]=f[i-1]*p+a[i]-'a'+1,mi[i]=mi[i-1]*p;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(Hash(l1,r1)==Hash(l2,r2))printf("Yes\n");
        else printf("No\n");
    }
}
已复制