图书管理

思路

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

代码

#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;
}