信奥一本通——哈希 里的例题2
题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1456
题目描述：两个命令，一个是进一本名字为s的图书，一个是找现有的图书里有没有名字为s的图书，如果有输出 “噎死” “yes”，没有输出 “no” 。
这道题基础思路是用哈希，将书名的字符串转换成相应的哈希值，再进行查找。
但是
书名的长度最长200，这么大的字符串哈希值看着都腿软。
那怎么办呢？
在c++中有一种数据结构叫vector，是一个动态2维数组，可以将一维的数向下扩充成2维（甚至三维）。
那么，我们就可以在哈希的基础上，用vector进行进一步判断了。
将某串的哈希值模上个质数，然后将原串存在相应 vector [哈希值] 的地方
就像这样：
v[we/*相应哈希值*/].push_back(a);
下面完整代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int b=31;//工具质数 4 int we,q; 5 string a,c; 6 vector<string> v[30000];//必须是string类型的 7 int main(){ 8 int n; 9 cin>>n;10 for(int i=0;i<n;i++){11 cin>>c;12 if(c=="add"){13 getline(cin,a);//因为有空格，所以用这个 14 we=1;15 for(int j=0;j<a.size();j++){16 we=(we*b+(long long)a[j])%23333;//求哈希值 17 }18 v[we].push_back(a);//将字符串存进去 19 }20 if(c=="find"){21 getline(cin,a);22 we=1;23 for(int j=0;j<a.size();j++){24 we=(we*b+(long long)a[j])%23333;25 }//同上 26 q=0;27 for(int j=0;j<(int)v[we].size();j++){28 if(v[we][j]==a){//判断字符串是不是相等 29 cout<<"yes"<<endl;30 q=1;31 break;//这里可是坑坏了，如果不写break它会打出很多"yes"，要不然就在上面查重 32 }33 }34 if(q==0){//变量控制 35 cout<<"no"<<endl;36 }37 }38 }39 }
完美结束
