哈希表

哈希表是由哈希函数+链表结构共同实现，链表中储存哈希值相同的元素信息，以降低将元素全部存在一个桶里的空间复杂度，同时优秀的哈希函数可以保证数据的平均分配

例题

雪花判重

见进阶指南 P63

字符串哈希

利用一个哈希函数，将任意长度的字符串映射为一个非负整数，并且冲突的几率几乎为0。
过程： 取一个质数P，把字符串看成一个P进制数，将P进制数转化为10进制数后，进行取模操作，得到该字符串的哈希值
一般，取P=131或13331，此时哈希函数出现冲突的概率极低，在有需要时，可以多取几组P和M，使得冲突概率几乎为0，只需要hash值相同，即可认为两个字符串相同。
通常，取模的M为2^64，即unsigned long long 的取值范围，可以直接用自动溢出来替代低效的取模操作。
同时，对于字符串的各种操作可以直接反应在hash值上，例如在首尾添加，取出中间一段的hash值等，均可以由原hash值计算得到

例题

兔子与兔子

见进阶指南P66，即要求判断两只兔子的DNA是否相同
代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

ULL h[1000005],p[1000005];
int t=131,m,l,r,ll,rr;
char s[1000005];

inline ULL get(int l,int r){  //取出中间的一段
    return h[r]-h[l-1]*p[r-l+1];
}

bool check(int l,int r,int ll,int rr){
    ULL t=get(l,r);
    ULL tt=get(ll,rr);
    return t==tt;
}

int main(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    p[0]=1;
    for (int i=1;i<=len;++i){
        h[i]=h[i-1]*t+s[i]-'a'+1;
        p[i]=p[i-1]*t;
    }
    cin>>m;
    for (int i=1;i<=m;++i){
        scanf("%d %d %d %d",&l,&r,&ll,&rr);
        if (check(l,r,ll,rr)) puts("Yes");
        else puts("No");
    }
    return 0;
}

最长回文子串

求出一段字符串的最长回文子串，做两次hash，然后枚举中心点即可，再配合二分答案
见进阶指南 P67，也可以采用manacher，在O（n）时间内得到答案

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

ULL p[500005],pr[500005],re[500005],t=13331;
int n;
char s[500005];

inline ULL getpr(int l,int r){
    return pr[r]-pr[l-1]*p[r-l+1];
}

inline ULL getre(int l,int r){
    return re[l]-re[r+1]*p[r-l+1];
}


int get(int m){
    int l=0,r=min(m-1,n-m),mid,ans;
    while (l<=r){
        mid=(l+r)>>1;
        if (getpr(m-mid,m)==getre(m,mid+m)){
            l=mid+1;
            ans=mid*2+1;
        }else{
            r=mid-1;
        }
    }
    return ans;
}

int gett(int m){
    int m2=m+1;
    int l=0,r=min(m-1,n-m2),mid,ans;
    while (l<=r){
        mid=(l+r)>>1;
        if (getpr(m-mid,m)==getre(m2,mid+m2)){
            l=mid+1;
            ans=mid*2+2;
        }else{
            r=mid-1;
        }
    }
    return ans;
}

void solve(){
    int ans=0;
    n=strlen(s+1);
    for (int i=1;i<=n;++i) pr[i]=pr[i-1]*t+s[i]-'a'+1;
    for (int i=n;i>=1;--i) re[i]=re[i+1]*t+s[i]-'a'+1;
    for (int i=1;i<=n;++i) ans=max(ans,get(i));
    for (int i=1;i<=n-1;++i) ans=max(ans,gett(i));
    printf("%d\n",ans);
}

int main(){
    p[0]=1;
    for (int i=1;i<=500000;++i) p[i]=p[i-1]*t;
    while (scanf("%s",s+1)!=EOF) solve();
    return 0;
}

后缀数组

题面见 进阶指南 P67
代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
typedef unsigned long long ULL;

ULL h[MAXN],p[MAXN];
int t=131,sa[MAXN],height[MAXN],n;
char s[MAXN];

inline ULL get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

int getL(int a,int b){
    int l=0,r=min(n-a+1,n-b+1),mid,ans;
    while (l<=r){
        mid=(l+r)>>1;
        if (get(a,a+mid-1)==get(b,b+mid-1)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

bool cmp(int x,int y){
    int tmp=getL(x,y);
    return s[x+tmp]<s[y+tmp];
}

int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    p[0]=1;
    for (int i=1;i<=n;++i){
        h[i]=h[i-1]*t+s[i]-'a'+1;
        p[i]=p[i-1]*t;
        sa[i]=i;
    }
    sort(sa+1,sa+n+1,cmp);
    for (int i=2;i<=n;++i) height[i]=getL(sa[i],sa[i-1]);
    for (int i=1;i<=n;++i) printf("%d ",sa[i]-1);puts("");
    for (int i=1;i<=n;++i) printf("%d ",height[i]);puts("");
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/75/