[模板] 字符串hash

首先先奉上一篇博客

然后奉上洛谷模板题

单模数 （80）

#include <cstdio>
#include <cstring> 
#include <algorithm>
#define mod 19260817
#define MAXN 10005
#define base 131

char str[1505];
unsigned long long h[MAXN];

inline unsigned long long hash(){
    int len = strlen(str);
    unsigned long long ans = 0;
    for(register int i=0;i<len;++i){
        ans = ( ans * base + (unsigned long long)str[i] ) % mod;
    }
    return ans;
}

int main(){
    
    int N;
    scanf("%d\n",&N);
    for(register int i=1;i<=N;++i){
        scanf("%s",str);
        h[i] = hash();
    }
    
    std::sort(h+1,h+N+1);
    
    int ans = 0;
    h[0]=1926081800;
    for(register int i=1;i<=N;++i){
        if(h[i]!=h[i-1])ans++;
    }
    
    printf("%d\n",ans);
    return 0;
} 

自然溢出 AC

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 10005
#define base 131
 
unsigned long long h[MAXN];
char str[1505];

inline unsigned long long hash(){
    int len = strlen(str);
    unsigned long long ans = 0; 
    for(register int i=0;i<len;++i){
        ans = ans * base + (unsigned long long)str[i];
    }
    return ans;
}


int main(){
    
    int N;
    scanf("%d\n",&N);
    for(register int i=1;i<=N;++i){
        scanf("%s",str);
        h[i] = hash();
    }
    
    std::sort(h+1,h+1+N);
    int ans = 0;
    for(register int i=1;i<=N;++i){
        if(h[i]!=h[i-1])ans++;
    }
    printf("%d",ans);
    return 0;
}

大模数 AC

#include <cstdio>
#include <cstring> 
#include <algorithm>
#define mod 212370440130137957ll
#define MAXN 10005
#define base 131

char str[1505];
unsigned long long h[MAXN];

inline unsigned long long hash(){
    int len = strlen(str);
    unsigned long long ans = 0;
    for(register int i=0;i<len;++i){
        ans = ( ans * base + (unsigned long long)str[i]) % mod;
    }
    return ans;
}
int main(){
    
    int N;
    scanf("%d\n",&N);
    for(register int i=1;i<=N;++i){
        scanf("%s",str);
        h[i] = hash();
    }
    
    std::sort(h+1,h+N+1);
    int ans = 0;
    for(register int i=1;i<=N;++i){
        if(h[i]!=h[i-1])ans++;
    }
    printf("%d",ans);
    return 0;
} 

双hash AC

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

#define mod1 19260817
#define mod2 19660813
#define MAXN 10005
#define base 131

char str[1505];

struct Node{
    unsigned long long a,b;
}h[MAXN];

int N;

inline bool cmp(Node x,Node y){return x.a<y.a;}
inline Node hash(){
    int len = strlen(str);
    unsigned long long ans1=0,ans2=0;
    for(register int i=0;i<len;++i){
        ans1 = ( ans1 * base + (unsigned long long)str[i] ) % mod1;
        ans2 = ( ans2 * base + (unsigned long long)str[i] ) % mod2;
    }
    return (Node){ans1,ans2};
}

int main(){
    
    scanf("%d\n",&N);
    for(register int i=1;i<=N;++i){
        scanf("%s",str);
        h[i] = hash();
    }
    
    std::sort(h+1,h+1+N,cmp);
    int ans = 0;
    for(register int i=1;i<=N;++i){
        if(h[i].a!=h[i-1].a||h[i].b!=h[i-1].b)ans++;
    }
    printf("%d",ans);
    return 0;
}