图书管理
程序员文章站
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; }