社区讨论

不理解双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 条回复,欢迎继续交流。

正在加载回复...