10个过了9个
见下图
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int m=19997;
string strHash[m]{};
int h1(string k){
int ans=0;
int bitWeight=1;
for(int i=0;i<k.length();i++){
int bitValue=int(k[i]);
ans=(ans+bitValue*bitWeight)%m;
bitWeight=(bitWeight*128)%m;
}
return ans;
}
int h2(string k){
int ans=0;
int bitWeight=1;
for(int i=0;i<k.length();i++){
int bitValue=int(k[i]);
ans=(ans+bitValue*bitWeight)%(m-1);
bitWeight=(bitWeight*128)%(m-1);
}
ans+=1;
return ans;
}
int h(string k,int i){
return (h1(k) + i*h2(k)) %m;
}
void putInHash(string toPush){
for(int i=0;i<m;i++){
int place =h(toPush,i)-1;
if(strHash[place]==""){
strHash[place]=toPush;
//cout<<"placed one string at"<<place<<"\n";
return;
}
if(strHash[place]==toPush) return;
}
//cout<<"error\n";
}
int checkHashAmount(){
int amount=0;
for(int i=0;i<m;i++){
if(strHash[i]!="") amount++;
}
return amount;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
string inNow;
cin>>inNow;
putInHash(inNow);
}
cout<<checkHashAmount();
}
用的是双重散列(就是用两个除法散列函数生成一个函数进行开放选址) 实在是不知道怎么回事了,大佬帮忙看看