感觉这道题真好啊，原来在做PAT的时候，都没有做过双散列结构的开放地址法，今天学到了，这个方法真的好，但是总感觉这道题如果像 《挑战》上这么做的话，应该会很费时吧，用了一下unordered_map也能过，之前看算法笔记的时候，就看到对于字符串的哈希，有很多种的哈希方法，而且代码都很简单，特别是有一种的方法的冲突碰撞的概率要小于百分之10，之后有空的话要看一下。
#include<cstdio>
#include<cstring>
using namespace std;
const int m = 1046527;
int mp[256];char H[m][13];
void init(){//使用的进制是4进制
memset(H,0,sizeof H);
mp['C'] = 1;
mp['G'] = 2;
mp['T'] = 3;
}
int strToInt(char* str){
int res = 0,len = strlen(str);
for(int i = 0;i < len;i++) res = res * 4 + mp[str[i]];
return res;
}
int h1(int code){ return code % m;}
int h2(int code){ return 1 + code % (m - 1);}
void insert(char* name,int n){
int IntName = strToInt(name);
int h1ans = h1(IntName);
int h2ans = h2(IntName);
for(int i = 0;i <= n;i++){//数学上好像是证明了，如果到n都没有找到的话，呢么就是没有空位了
if(strlen(H[h1ans]) == 0){strcpy(H[h1ans],name);break;}
h1ans += h2ans;
h1ans = h1ans % m;
}
}
bool find(char* name,int n){
int IntName = strToInt(name);
int h1ans = h1(IntName),h2ans = h2(IntName);
while(n--){
if(strlen(H[h1ans]) == 0) return false;
else if(!strcmp(H[h1ans],name)) return true;
h1ans += h2ans;
h1ans = h1ans % m;
}
return false;
}
int main(){
//FILE* fp = freopen("C:\\Users\\Lenovo\\Desktop\\1.txt","w",stdout);
//FILE* fp2 = freopen("C:\\Users\\Lenovo\\Desktop\\2.txt","r",stdin);
init();
int n;scanf("%d",&n);
for(int i = 0;i < n;i++){
char op[12],name[15];
scanf("%*c%s %s",op,name);
if(op[0] == 'i') insert(name,n);
else {
if(find(name,n))printf("yes\n");
else printf("no\n");
}
}
//fclose(fp);
//fclose(fp2);
return 0;
}
