ZJM 为了准备霍格沃兹的期末考试，决心背魔咒词典，一举拿下咒语翻译题
题库格式：[魔咒] 对应功能
背完题库后，ZJM 开始刷题，现共有 N 道题，每道题给出一个字符串，可能是 [魔咒]，也可能是对应功能
ZJM 需要识别这个题目给出的是 [魔咒] 还是对应功能，并写出转换的结果，如果在魔咒词典里找不到，输出 “what?”
首先列出魔咒词典中不超过100000条不同的咒语，每条格式为：
[魔咒] 对应功能
其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。魔咒词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。
每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果在词典中查不到，就输出“what?”
[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
light the wand
accio
what?
what?
这是一道利用字符串哈希解决的经典问题。
1. 什么是字符串哈希？
字符串哈希指的就是将一个字符串转换为一个值进行处理的方法。
公式如下：
一个长度为n的字符串，
hash =（字符1值 * seed^n + 字符2值 * seed^(n-1) ... + 字符n值 * seed^1）% mod
字符值可以有多种规定方式：
1）如都是由大写字母或小写字母组成的字符串，则可以用字母顺序来作为值。如a = 1，b = 2…
2）如除字母外包含其他多种字符，可以用ascii码作为值。
seed取值
seed常见的取值为7、17、131
取余处理
取余处理是为了保证不会溢出造成结果错误。
1）mod取1e9+7
2）不需要mod，而是将数据类型换做unsigned long long，利用该数据类型的自然溢出处理取余。
2. 多种情况的字符串哈希计算
除去给出一个字符串求哈希值以外，我们还有可能遇到将两个字符串合并或者原字符串中某些字符发生变动的情况。而在这两种情况下，同样可以求出新字符串的哈希值。
一个易懂的小🌰：
原字符串的哈希值 - 被替换字符x的值 * seedi， 即为去掉字符x后的字符串哈希值。而再加上替换字符y的值 * seedi ，就是去掉原字符后的字符串加上新字符的字符串哈希值。
其实这个也很好理解。在新字符串中字符串1在前半部分，字符串2在后半部分，若对这个新字符串进行哈希计算会发现，字符串1 中所有字符对应所乘的seed的幂将会增加len2（字符串2的长度）。这是因为字符串1中的每个字符所在的字符串的长度增加了len2，因此幂要从len2+len1开始递减，而原本是从len1。
因此将字符串1的哈希值乘以seedlen2再加上字符串2的哈希值，再求模即为合并后的字符串哈希值。
3. 注意事项
利用哈希问题求解值得注意的有几点：
4. 适合的问题类型
字符串哈希值非常适合快速比较和字符串之间的映射。
根据题目可以发现，我们需要根据题目给出的数据建立咒语到功能的相互映射。因此显然这就是一道需要字符串哈希解决的问题。
那么为什么不能直接建立字符串到字符串的映射呢？是因为根据题目要求需要建立双向映射，如果直接存储字符串就意味着需要将每个字符串存储两次，这种做法会导致超容。
因此我们需要将每个字符串的存储次数减小到一次。那么就可以用map分别建立咒语字符串哈希值到对应功能在数组中的下标以及功能字符串哈希值到对应咒语在数组中的下标。
首先判断题目给出的查询数据是咒语还是功能，然后将查询字符串求哈希值，查找该哈希值在对应的map中是否存在。若不存在说明没有该咒语或功能，若存在则从对应数组中取出其映射下标位置的字符串。
这道题目主要的处理都是对于字符和字符串，因此对输入数据的细节十分重要。
spell[trans(s2)] = tot; //用功能哈希值映射咒语下标
functions[trans(s1)] = tot; //用咒语哈希值映射功能下标
spell2[tot++] = s1; //将咒语和功能存储起来
func2[tot++] = s2;
但是，改变一下顺序后的写法就是正确的：
spell2[tot] = s1; //将咒语和功能存储起来
func2[tot] = s2;
spell[trans(s2)] = tot; //用功能哈希值映射咒语下标
functions[trans(s1)] = tot; //用咒语哈希值映射功能下标
tot++;
//
//
// main.cpp
// lab1
//
//
#include <string>
#include <map>
#include <string.h>
#include <memory.h>
#include <iostream>
using namespace std;
//从功能的字符串哈希值映射到对应咒语下标
//从咒语的字符串哈希值映射到对应功能下标
map<unsigned long long,int> spell,functions;
string spell2[100001],func2[100001]; //存储咒语、功能
unsigned long long t = 7;
unsigned long long trans(string s) //将字符串转换为值
{
unsigned long long ans = 0,seed = t;
for(int i = s.size() - 1 ; i >= 0 ; i-- )
{
ans += (unsigned long long)s[i] * seed;
seed *= t;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
string s1,s2,s;
int tot = 0;
while( cin>>s1 )
{
if( s1 == "@END@" )
break;
getchar(); //把咒语和功能之间的空格吃掉
getline(cin,s2);
s1.erase(0, 1); //删除咒语首尾的[]
s1.erase(s1.size() - 1,1);
spell2[tot] = s1; //将咒语和功能存储起来
func2[tot] = s2;
spell[trans(s2)] = tot; //用功能哈希值映射咒语下标
functions[trans(s1)] = tot; //用咒语哈希值映射功能下标
tot++;
}
int n = 0;
cin>>n;
getchar(); //吃掉n之后的提行符
for( int i = 0 ; i < n ; i++ )
{
getline(cin,s);
if( s[0] == '[' && s[s.size() - 1] == ']' ) //若输入的是咒语
{
s.erase(0, 1);
s.erase(s.size() - 1,1);
auto it = functions.begin(); //查看该咒语的哈希值是否存在
it = functions.find(trans(s));
if( it != functions.end() ) //存在则输出对应功能
cout<<func2[it->second]<<endl;
else
cout<<"what?"<<endl;
}
else
{
auto it = spell.begin(); //查看该功能哈希值是否存在
it = spell.find(trans(s));
if( it != spell.end() ) //存在则输出对应咒语
cout<<spell2[it->second]<<endl;
else
cout<<"what?"<<endl;
}
}
return 0;
}