无意中看到这题，就切了一下，感觉这题很适合刚刚接触散列表和字符串处理的朋友，直接对字符串 hash 就可以了，用 map 暴力不知道能不能过，没有尝试过。
我的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX = 210000;
const int mod = 100007;
struct Node {
Node* ne;
char st[81];
} hash[MAX], *h[mod], *cur;
unsigned int BKDHash(char* s) {
unsigned int seed = 131;
unsigned int ret = 0;
while (*s) {
ret = ret * seed + *s++;
}
return (ret & 0x7FFFFFFF) % mod;
}
int getId(char* s) {
int code = BKDHash(s);
Node* ptr = h[code];
while (ptr) {
if (strcmp(ptr->st, s) == 0) {
return ptr - hash;
} else {
ptr = ptr->ne;
}
}
strcpy(cur->st, s);
cur->ne = h[code];
h[code] = cur++;
return cur - hash - 1;
}
int find(char* s) {
int code = BKDHash(s);
Node* ptr = h[code];
while (ptr) {
if (strcmp(ptr->st, s) == 0) {
return ptr - hash;
} else {
ptr = ptr->ne;
}
}
return -1;
}
int main() {
char s[100], *p;
int id, n;
cur = hash;
memset(h, 0, sizeof(h));
while (scanf("%s", s), s[0] != '@') {
getId(s);
getchar();
gets(s);
getId(s);
}
scanf("%d", &n);
gets(s);
while (n--) {
gets(s);
id = find(s);
if (id == -1) {
puts("what?");
} else {
p = hash[id ^ 1].st;
if (p[0] != '[') {
puts(p);
} else {
p++;
while (*p != ']') {
putchar(*p++);
}
puts("");
}
}
}
return 0;
}
|