【LOJ10034】图书管理（哈希表，字符串）

problem

维护一个集合，支持以下两种操作
1. 加入一个字符串s
2. 查询集合中是否存在字符串s

solution

• 维护一个哈希表，判断字符串是否已出现过。

codes

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 3e4+10, mod1 = 1e6+3, mod2 = 1e6+9, p1 = 47, p2 = 79;

int tot, head[mod1], nxt[maxn], val[maxn];//RE
void insert(int x, int y){
    nxt[++tot] = head[x];
    head[x] = tot;
    val[tot] = y;
}
bool query(int x, int y){
    for(int i = head[x]; i; i = nxt[i])
        if(val[i]==y)return true;
    return false;
}

int main(){
    int n;  scanf("%d",&n);
    while(n--){
        char op[10], s[210];
        cin>>op;
        gets(s);//读入剩余的一整行
        //双哈希，两个关键字决定一个字符串，减小误差
        int len = strlen(s), sum1=0, sum2=0;
        for(int i = 0; i < len; i++){
            sum1 = (sum1*p1+s[i])%mod1;//RE
            sum2 = (sum2*p2+s[i])%mod2;
        }
        if(op[0]=='a')insert(sum1,sum2);
        else {
            if(query(sum1,sum2))printf("yes
");
            else printf("no
");
        }
    }
    return 0;
}