信奥一本通——哈希 里的例题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 }

完美结束

05-02 11:16