图书管理

https://loj.ac/problem/10034

题目描述

  设计一个系统支持两个操作：

  (①)加入一个字符串(s)；

  (②)查找是否存在一个字符串。

思路

  我们这里的要求是维护一个可快速查找、插入字符串的数据结构。我们这里可以用(Hash)表，也就是散列表来储存。我们用使用双(Hash)，生成两个值，其中一个作为散列表的标号，还有记录值。那么这样会形成一个由数组延伸出来的列表，本质上与前向星相似，因此我们也可以用类似前向星遍历的方法进行寻找。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod1=1e6+3,mod2=1e6+9,p1=47,p2=79;
const int MAXN=30005;
char s[10],name[220];
int tot,nxt[MAXN],poi[mod1+5],key[MAXN];
void insert(int x,int y)
{
    nxt[++tot]=poi[x];
    poi[x]=tot;
    key[tot]=y;
}
bool query(int x,int y)
{
    for(int i=poi[x];i;i=nxt[i])
        if(key[i]==y)return 1;
    return 0;
}
int main() 
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf(" %s",s);
        gets(name);
        int len=strlen(name);
        int sum1=0,sum2=0;
        for(int i=0;i<len;i++)
        {
            sum1=(sum1*p1+name[i])%mod1;
            sum2=(sum2*p2+name[i])%mod2;
        }
        if(s[0]=='a')insert(sum1,sum2);
        else
        {
            if(query(sum1,sum2))printf("yes
");
            else printf("no
");
        }
    }
    return 0;
}