社区讨论

一样的哈希函数和质数,一样的字符串,为什么哈希值不一样

P3370【模板】字符串哈希参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lv6u3mtp
此快照首次捕获于
2024/04/19 23:37
2 年前
此快照最后确认于
2024/04/20 10:24
2 年前
查看原帖
CPP
#include <cstdio>
#include <cstring>
#include<iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
struct data
{
    ull x,y;
}a[10010];
char s[10010];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;
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 comp(data a,data b)
{
    return a.x<b.x;
}
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        a[i].x=hash1(s);
        a[i].y=hash2(s);
        cout<<a[i].x<<' '<<a[i].y<<endl; 
    }
    sort(a+1,a+n+1,comp);
    printf("%d\n",ans);
}
这是题解的答案
CPP
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;

const ull mod1=19260817;
const ull mod2=19660813;
const ull base=131;

std::pair<ull,ull> a[10007];
int n,ans=1;

char s[10007];

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>s;
        for(auto ele:s){
            a[i].first=(a[i].first*base+(ull)ele)%mod1;
            a[i].second=(a[i].second*base+(ull)ele)%mod2;
        }
        cout<<a[i].first<<' '<<a[i].second<<endl;
    }
    std::sort(a+1,a+n+1);

    for(int i=2;i<=n;++i){
        if(a[i].first!=a[i-1].first||a[i].second!=a[i-1].second){
            ++ans;
        }
    }
    cout<<ans<<endl;
}
这是我18tps的hash
对这样例进行双hash,求出来hash值的不一样

回复

1 条回复,欢迎继续交流。

正在加载回复...