题目链接:
https://vjudge.net/problem/POJ-2503
题目大意:
就像查找一本字典, 根据输入的条目和要查询的单词, 给出查询结果 (每个单词长度不超过 10)
解题思路:
map 容器可以直接过, 不过为了练习 hash, 写了个 hash 也可以过
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<map>
- #include<set>
- #include<cmath>
- #include<algorithm>
- #include<vector>
- #include<sstream>
- #define lowbot(i) (i&(-i))
- //#define Rotate(a, b) node(a.x + a.y - b.y, a.y + b.x - a.x)
- using namespace std;
- typedef long long ll;
- const int maxn = 1000 + 10;
- const int mod = 99973;// 一般为靠近总数的素数
- struct Hashtable
- {
- string s, t;//hash 存的值
- Hashtable * next;
- Hashtable()
- {
- next = 0;
- }
- };
- Hashtable * Hash[mod];
- void Hash_Insert(string s, string t)//s 对应 t
- {
- int key = 0;
- for(int i = 0; i <s.size(); i++)
- key = (key * 26 + (s[i] - 'a')) % mod;
- if(!Hash[key])// 该 key 第一个元素
- {
- Hashtable * p = new Hashtable;
- p->s = s;
- p->t = t;
- Hash[key] = p;
- }
- else
- {
- Hashtable *p = Hash[key];
- while(p->next)p=p->next;
- Hashtable* temp = new Hashtable;
- temp->s = s;
- temp->t = t;
- p->next = temp;
- }
- }
- void Find(string s)
- {
- int key = 0;
- for(int i = 0; i <s.size(); i++)
- key = (key * 26 + (s[i] - 'a')) % mod;
- if(Hash[key])
- {
- Hashtable * temp = Hash[key];
- while(temp)
- {
- if(temp->s == s)
- {
- cout<<temp->t<<endl;
- return;
- }
- temp = temp->next;
- }
- }
- cout<<"eh"<<endl;
- return;
- }
- int main()
- {
- string s, s1, s2;
- while(getline(cin, s))
- {
- if(s.size() == 0)break;
- stringstream ss(s);
- ss>> s1>> s2;
- Hash_Insert(s2, s1);
- }
- while(cin>> s2)
- {
- Find(s2);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2575214.html