刚学哈希。。 按着hallo算法里面教的写的,只过了四个点 不知道问题出在哪了 求大佬教教
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull base=131;
int prime=233317;
ull mod=212370440130137957ll;
int ans = 0;
struct Pair
{
ull key;
string val;
Pair(int key,string val)
{
this->key = key;
this->val = val;
}
};
vector<Pair*> mp(150005);
//原始输入 -> key
ull Hash(string res)
{
ull key = 0;
for(int i = 0;res[i]!=0;i++)
{
key += (base*key + res[i])%mod;
}
return key % 1000000007;
}
bool search(ull key,string val)
{
ull index = key % 10000;
if(mp[index] != nullptr)
{
return true;
}else{
return false;
}
}
void put(ull key,string val)
{
ull index = key % 10000;
mp[index] = new Pair(key,val);
ans++;
}
int main()
{
int n;
cin>>n;
while(n--)
{
string temp;
cin>>temp;
ull key = Hash(temp);
if(!search(key,temp))
{
put(key,temp);
}
}
cout<<ans;
return 0;
}