用c++和BKDRHash方法解决下述问题:描述 Akko正在Luna Nova Magic Academy学习魔法。据说魔法世界中有10^5种不同的诅咒。阿卡很难记住所有这些。幸运的是,梅里迪斯教授说她可以帮助阿卡制作一本诅咒词典。当Akko听到诅咒时,字典会告诉她诅咒的效果。此外,当Akko想做某事时,字典会为她找到诅咒。如果没有这样的诅咒,字典将是沉默的。你能写一个程序来重现诅咒词典吗?输入 每个测试用例将包含不超过 10^5 个诅咒。每个诅咒都会像“[名称]效应”。诅咒的名称和效果将只包含小写字母。“]”和它后面的字符串之间只有一个空格。名称长度不超过20,效果长度不超过80。字典的末尾是一行“END”。在所有诅咒之后,将有一个整数 N (1<=N<1000),后跟 N 个查询。每个查询都将是一个“[诅咒名称]”或“诅咒效果”。每个输入文件中只有一个测试用例。输出 对于每个测试用例,您必须按其名称输出诅咒的效果或按其效果输出诅咒的名称。如果没有满足条件的诅咒,请打印“沉默”。提示 哈希字符串 gets() 在 C++14 中被弃用,改用 getline。对于 char arr[],请使用 cin.getline(arr,sizeof(arr));对于字符串 arr,请使用 getline(cin, arr);
时间: 2024-03-10 17:49:32 浏览: 109
好的,我可以为您提供一个示例代码,来实现这个功能。由于您要求使用BKDRHash方法,我将使用它来进行字符串的哈希。
首先,我们需要定义一个结构体来存储诅咒的名称和效果:
```
struct Curse {
string name;
string effect;
};
```
然后,我们定义一个哈希函数,使用BKDRHash方法:
```
unsigned int BKDRHash(const string& str) {
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash = hash * seed + str[i];
}
return hash;
}
```
接下来,我们使用哈希表来存储所有的诅咒:
```
const int MAXN = 100005;
vector<Curse> curseTable[MAXN];
int main() {
// 读入诅咒
string line;
while (getline(cin, line)) {
if (line == "END") break;
int pos = line.find(" ");
string name = line.substr(1, pos - 1);
string effect = line.substr(pos + 1);
unsigned int hash = BKDRHash(name);
curseTable[hash].push_back({name, effect});
}
// 处理查询
int n;
cin >> n;
getchar(); // 读取换行符
for (int i = 0; i < n; i++) {
getline(cin, line);
if (line[0] == '[') {
// 查询名称
string name = line.substr(1, line.length() - 2);
unsigned int hash = BKDRHash(name);
for (auto& curse : curseTable[hash]) {
if (curse.name == name) {
cout << curse.effect << endl;
goto found;
}
}
cout << "沉默" << endl;
} else {
// 查询效果
for (int j = 0; j < MAXN; j++) {
for (auto& curse : curseTable[j]) {
if (curse.effect == line) {
cout << "[" << curse.name << "]" << endl;
goto found;
}
}
}
cout << "沉默" << endl;
}
found:;
}
return 0;
}
```
代码中使用了一个哈希表来存储所有的诅咒。对于查询,如果查询的是名称,则根据名称的哈希值在哈希表中查找所有名称为该值的诅咒,并输出其效果;如果查询的是效果,则遍历所有诅咒,找到效果匹配的诅咒,并输出其名称。
需要注意的一点是,由于查询的时候可能会有多个诅咒的名称或效果相同,因此在哈希表中我们使用了一个vector来存储所有的诅咒。
希望这个示例代码可以帮助您解决问题。
阅读全文