ハッシュ法の利用（螺旋本）

はじめに

螺旋本に挑戦中です。今回はHashについてのコードを書きました。

問題

以下の命令を実行する簡易的な「辞書」を実装してください。

• insert str: 辞書に strを追加する。
• find str: 辞書に str が含まれる場合 'yes'と、含まれない場合 'no'と出力する。

回答

# include <bits/stdc++.h>
# define FOR(i, a, b) for (int i = (a); i < (b); ++i)
# define REP(i, n) FOR(i, 0, n)
# define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
# define EXIST(s, e) ((s).find(e) != (s).end())
# define SORT(c) sort((c).begin(), (c).end())
# define dump(x) cerr << #x << " = " << (x) << endl;
# define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;
# define ALL(a) (a).begin(), (a).end()
# define PB push_back
# define MP make_pair
# define SZ(a) int((a).size())

using namespace std;

# define M 1777771

class Dictionary{
    private:
        vector<string> data;
        map<int, string> m;
    public:
        void insert(string str);
        void hash_Insert(string str);
        bool find(string str);
        bool hash_Find(string str);
        int get_Kay(string str);
        int hash_1(int kay);
        int hash_2(int kay);
};

int Dictionary::hash_1(int kay){ return kay%M; }
int Dictionary::hash_2(int kay){ return 1+(kay%(M-1)); }

int Dictionary::get_Kay(string str){
    int k = 0;
    REP(i, (int)str.length()){
        k += (int)str[i] * pow(5, i);
    }
    return k;
}

void Dictionary::insert(string str){
    if (!Dictionary::find(str)) data.PB(str);
}
void Dictionary::hash_Insert(string str){
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while(true){
        hashed_Kay = hash_1(kay) + i*hash_2(kay);
        if(m[hashed_Kay] == "" or m[hashed_Kay] == str) break;
    }
    m[hashed_Kay] = str;
}

bool Dictionary::find(string str){
    if(std::find(ALL(data), str) != data.end()) return true;
    else return false;
}
bool Dictionary::hash_Find(string str){
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while(true){
        hashed_Kay = hash_1(kay) + i*hash_2(kay);
        if(m[hashed_Kay] == str) return true;
        else if(m[hashed_Kay].length() == 0) return false;
    }
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    string op, word;
    Dictionary dic;
    
    REP(_, n){
        cin >> op >> word; 
        if (op[0] == 'i') dic.hash_Insert(word);
        else if(dic.hash_Find(word)) cout << "yes" << "\n";
        else cout << "no" << "\n";
    }  
}

結果

時間切れとなりました

考察

実は一度自力実装を諦め、参考書の回答をみてC++で記述したのですが通せないので原因がよくわかっていません。こういう場合はケアレスミスがあるということが多いのでよくよく見直してみたいと思います。