欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

图书管理

程序员文章站 2023-11-20 09:46:46
"题目描述" 思路 使用字符串产生两个哈希值,一个哈希值决定链表的头,另一个哈希值决定在某个链表头的后面的某个位置。 代码 c++ include include include int n; char a[10], b[209]; int bs = 37, h1 = 90001, h2 = 900 ......

思路

使用字符串产生两个哈希值,一个哈希值决定链表的头,另一个哈希值决定在某个链表头的后面的某个位置。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
int n;
char a[10], b[209];
int bs = 37, h1 = 90001, h2 = 90007;
int head[90001], nxt[30005], ver[30005], ht;
int res1, res2, len;

bool find(int x, int y) {
    for (int i = head[x]; i; i = nxt[i]) {
        if (ver[i] == y) return true;
    }
    return false;
}

void add(int x, int y) {
    if (!find(x, y)) {
        nxt[++ht] = head[x];
        ver[ht] = y;
        head[x] = ht;
    }
}


int main() {
    // 产生哈希表的两个数
    // int cnt = 0;
    // for (int i = 90001; cnt < 2; i += 2) {
        // bool flag = false;
        // for (int j = 3; j <= sqrt(i); ++j) {
            // if (i % j == 0) flag = true;
        // }
        // if (!flag) {
            // printf("%d\n", i);
            // cnt++;
        // }
    // }
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", a);
        gets(b + 1);
        len = strlen(b + 1);
        res1 = 0, res2 = 0;
        for (int i = 1; i <= len; ++i) {
            res1 = ((long long)res1 * bs % 90001 + b[i]) % 90001;
            res2 = ((long long)res2 * bs % 90007 + b[i]) % 90007;
        }
        if (strcmp(a, "add") == 0) {
            add(res1, res2);
        } else {
            if (find(res1, res2)) puts("yes");
            else puts("no");
        }
    }
    return 0;
}