原题链接

Your task is to write a program of a simple dictionary which implements the following instructions:

• insert *str*: insert a string str in to the dictionary

• find *str*: if the distionary contains str, then print 'yes', otherwise print 'no'

Input

In the first line n, the number of instructions is given. In the following n lines, n instructions are given in the above mentioned format.

Output

Print yes or no for each find instruction in a line.

Constraints

• A string consists of 'A', 'C', 'G', or 'T'

• 1 ≤ length of a string ≤ 12

• n ≤ 1000000

Sample Input 1

5
insert A
insert T
insert C
find G
find A

Sample Output 1

no
yes

Sample Input 2

13
insert AAA
insert AAC
insert AGA
insert AGG
insert TTT
find AAA
find CCC
find CCC
insert CCC
find CCC
insert T
find TTT
find T

Sample Output 2

yes
no
no
yes
yes
yes

首先考虑用set秒杀：

#include<bits/stdc++.h>
​
using namespace std;
​
set<string> S;
​
int main(){
    char ch[20];
    string s;
    int n;
    cin >> n;
    for(int i = 0;i < n;i ++){
        scanf("%s",ch);
        if(ch[0] == 'i'){
            cin >> s;
            S.insert(s);
        }
        else if(ch[0] == 'f'){
            cin >> s;
            if(S.find(s) != S.end()) cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }
    return 0;
}

 

嗯，确实可以秒了，但是这题的目的是为了应用一下散列法，所以还是老实地写了一下用散列法。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//M是用来对哈希值取模的
const int N = 1e6 + 10,M = 999997;
//采用拉链法来构造哈希表
list<string>L[N];
//哈希函数
int getchar(char ch){
    if(ch == 'A')return 1;
    else if(ch == 'C')return 2;
    else if(ch == 'G')return 3;
    else if(ch == 'T')return 4;
    else return 0;
}
int getkey(char ch[]){
    ll sum = 0,p = 1,i;
    for(int i = 0;i < strlen(ch);i ++){
        sum += p*getchar(ch[i]);
        p *= 5;
    }
    return sum%M;
}
​
int main(){
    char s[20];
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        cin >> s;
        char str[12];
//判断是insert还是find
        if(s[0] == 'i'){
            cin >> str;
            ll key = getkey(str);
//在对应哈希值的链表里插入这个元素
            L[key].push_back(str);
        }
        else if(s[0] == 'f'){
            cin >> str;
            int key = getkey(str);
//在对于哈希值的链表里查找对应元素
            list<string>::iterator iter = L[key].begin();
            for(;iter != L[key].end();iter ++){
                if(str == *iter){
                    cout << "yes" << endl;
                    break;
                }
            }
//迭代器指向链表end(),则没有找到相应元素
            if(iter == L[key].end())cout << "no" << endl;
        }
    } 
    return 0;
}

 

原书上的开放地址法感觉没有拉链法来得简洁明了。