欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串哈希

程序员文章站 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;
}

相关标签: 哈希表 字符串