社区讨论
一样的哈希函数和质数,一样的字符串,为什么哈希值不一样
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 条回复,欢迎继续交流。
正在加载回复...