題解0011：圖書管理（哈希、vector）
信奧一本通——哈希 里的例題2
題目鏈接：//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 }
完美結束
