社区讨论
不理解双hash错哪里了
P3370【模板】字符串哈希参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lpp7wbpc
- 此快照首次捕获于
- 2023/12/03 16:25 2 年前
- 此快照最后确认于
- 2023/12/03 19:00 2 年前
rt,除#3,#4,#5以外全部re,27pts
CPP#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int M = 23333;
int n, cnt = 0;
string linker[M + 3];
LL get_num(string str)
{
LL base = 3, len = str.length(), hash = 0;
for(LL i = 0; i < len; i ++)
{
hash = hash + 29 + int(str[i]) * base;
base *= 3;
}
return hash;
}
int h1(int k)
{ return (k + 2) % M + 7; }
int h2(int k)
{ return k % M + 3; }
int get_hash(int k)
{
int hash = 0;
for(int i = 0; ; i ++)
{
hash = (h1(k) + i * h2(k)) % M;
if(!linker[hash].size()) return hash;
}
return 0;
}
void insert(string key)
{ linker[get_hash(get_num(key) % M)] = key; }
int find(string str)
{
int k = get_num(str) % M, hash = 0;
for(int i = 0; i <= M; i ++)
{
hash = (h1(k) + i * h2(k)) % M;
if(linker[hash] == str) return 1;
else if(!linker[hash].length()) return 0;
}
return 0;
}
int main()
{
scanf("%d", &n);
while(n --)
{
string str;
cin >> str;
if(!find(str))
{
cnt ++;
insert(str);
}
}
printf("%d", cnt);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...