锐客网

  1. 首页 > it技术 > >

程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）

c++字符串HashMaphash

A - ZJM 与霍格沃兹（必做） 描述： 程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）
文章图片

输入： 程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）
文章图片

输出： 程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）
文章图片

样例： 输入：

[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?

思想： 整体思想是将字符串转化为对应hash值保存在map中，最后在map中搜索。
程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）
文章图片
计算hash值可以直接按照公式一个一个算，为了节约时间对于seed的乘法可以采用乘法快速幂计算。还可以采用提公因式计算，这样乘的次数取决于最高次。
程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）
文章图片
提公因子对应代码为：
long long Hash(string x) { long ans=0; for(int i=0; i

【程序设计思维与实践|程序设计思维与实践 Week15 作业 A - ZJM 与霍格沃兹（必做）】t1 = s.substr(0, s.find("] “)+1);
t2 = s.substr(s.find(”] “)+2, s.length() - s.find(”] ") - 1);
substr方法有效的提取想要的指定部分，然后将他们push进vector，对应的map记录，这里连续存放，方便后续提取。
对于查询的字符串直接
getline(cin, s); if(mp.find(Hash(s)) != mp.end() )判断是否存在在map中，若存在再进一步判断类型。
代码：
/* 字符串hash； */ #include #include #include #include #include #include #include #include using namespace std; const int inf = 1e9; const int seed=7; //hash种子； map mp; string s,t1,t2; vector> a; char c; int cnt,N; //返回hash值； long long Hash(string x) { long ans=0; for(int i=0; i>N; getchar(); while (N--) { getline(cin, s); if(mp.find(Hash(s)) != mp.end() ) {//找到； if(s[0]=='['){ string t=a[mp[Hash(s)]+1]; cout<

    推荐阅读


    上一篇：Git使用技巧之管理已有文件夹

    下一篇：C语言|C语言-socket（客户端-服务端通信）