字符串哈希
程序员文章站
2024-03-17 08:43:10
...
解题思路:
用一个map存储字符串哈希值到index的映射即可。index为对应的词条的标号(从1开始)。哈希函数使用bkdr哈希,每个字符对应的参数用其anscii码表示,mod采用unsigned int自然溢出的方式。读取字符的时候用getline读取一整行到一个string对象当中,读取完之后再对string对象进行处理。注意读取字符或字符串之前有cin或者scanf的话需要用getchar清空缓冲区。用string类型数组容易超容量,改用char类型二维数组。注意对数组赋值时使用string类的c_str()函数进行相应的转化。
参考代码:
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
map<unsigned int, int> mp1;
char s1[100005][25];
char s2[100005][85];
unsigned int seed=17;
unsigned int bkdr_hash(string s){
unsigned int rnt=0;
for (int i=0; i<s.size(); i++) {
rnt=rnt*seed+(unsigned int)(s[i]);
}
return seed*rnt;
}
int main(int argc, const char * argv[]) {
int cnt=0;
while (true) {
string str;
getline(cin,str);
if(str=="@aaa@qq.com") break;
cnt++;
string str1;
string str2;
int flag=1;
for (int i=1; i<str.size(); i++) {
if(str[i]==']'){
flag=2;
i++;
continue;
}
if(flag==1){
str1+=str[i];
}
else if (flag==2){
str2+=str[i];
}
}
mp1[bkdr_hash(str1)]=cnt;strcpy(s1[cnt],str1.c_str());
mp1[bkdr_hash(str2)]=cnt;strcpy(s2[cnt],str2.c_str());
}
int n;cin>>n;
getchar();
while (n--) {
string stri;
string stri2;
getline(cin,stri);
if(stri[0]=='['){
for (int i=1; i<stri.size()-1; i++) {
stri2+=stri[i];
}
if(mp1.find(bkdr_hash(stri2))==mp1.end())
cout<<"what?\n";
else{
cout<<s2[mp1[bkdr_hash(stri2)]]<<endl;
}
}
else{
if(mp1.find(bkdr_hash(stri))==mp1.end())
cout<<"what?\n";
else{
cout<<s1[mp1[bkdr_hash(stri)]]<<endl;
}
}
}
return 0;
}