ZJM 与霍格沃兹

ZJM 为了准备霍格沃兹的期末考试，决心背魔咒词典，一举拿下咒语翻译题
题库格式：[魔咒] 对应功能
背完题库后，ZJM 开始刷题，现共有 N 道题，每道题给出一个字符串，可能是 [魔咒]，也可能是对应功能
ZJM 需要识别这个题目给出的是 [魔咒] 还是对应功能，并写出转换的结果，如果在魔咒词典里找不到，输出 “what?”
Input
首先列出魔咒词典中不超过100000条不同的咒语，每条格式为：
[魔咒] 对应功能
其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。魔咒词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。
Output
每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果在词典中查不到，就输出“what?”
Sample Input

[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

Sample Output

light the wand
accio
what?
what?

思路:

首先，开map<string，string>肯定会爆内存；
那么就要使用hash函数将string映射成int；

哈希函数：目的就是为了产生字符串的哈希值，让不同的字符串尽量产生不同的哈希值的函数就是好的哈希函数，全然不会产生同样的哈希函数就是完美的。

BKDRHash是比较好的一个获取哈希值的方法，无论是在实际效果还是编码实现中，效果都是最突出的。

所以思路是:

详细请看代码(有详细注释)；

代码:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int maxn = 1e5 + 5;
const int seed = 7, mod = 1e9 + 7;
int N;
map<int, int> mp;
string s1[maxn], s2[maxn];unsigned int toInt(string &s)
{//hash函数   返回值是自动溢出int res = 0, index = 0;res = int(s[s.length() - 1]) * seed;for (int i = s.length() - 2; i >= 0; i--){res = ((res + int(s[i])) * seed) % mod;    //秦九韶}return res % mod;
}int main()
{string str, name, func;int index = 1;while (getline(cin, str) && str != "@END@"){int idx = str.find(']');name = str.substr(1, idx - 1);   //去掉[]func = str.substr(idx + 2);    //截取名称和功能mp[toInt(name)] = index;     //映射保存s1[index] = func;mp[toInt(func)] = index;s2[index] = name;index++;}cin >> N;getchar();for (int i = 1; i <= N; i++){getline(cin, str);if (str[0] == '['){//判断查询是名称还是功能int idx = str.find(']');name = str.substr(1, idx - 1);   //名称截取  去掉[]index = mp[toInt(name)];if (index == 0)  //index==0   没有找到cout << "what?" << endl;else{cout << s1[index] << endl;}}else{//与上面类似index = mp[toInt(str)];if (index == 0)cout << "what?" << endl;else{cout << s2[index] << endl;}}}return 0;
}