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

やったこと

以前の記事https://qiita.com/KenziTajima/items/e3ab73c23eee1e22895fでいただいたコメントを参考にAOJの問題ALDS1_4_C: Dictionaryに再挑戦しました。

改善したこと

以下の点について改善しました。

• pow()を使わない
• コンテナをmapからvectorに変更

以下ソースコード

# 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

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

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

int hash_Insert(string str, vector<string> data)
{
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while (true)
    {
        hashed_Kay = (hash_1(kay) + i * hash_2(kay)) % M;
        if (data[hashed_Kay] == "" or data[hashed_Kay] == str)
            return hashed_Kay;
        i++;
    }
}

bool hash_Find(string str, vector<string> data)
{
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while (true)
    {
        hashed_Kay = (hash_1(kay) + i * hash_2(kay)) % M;
        if (data[hashed_Kay] == str)
            return true;
        else if (data[hashed_Kay] == "")
            return false;
        i++;
    }
}

int main()
{
    int n;
    cin >> n;

    string op, word;
    vector<string> data(1000000);

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

結果

まだダメでした

考察

前回提示したソースコードには間違いがあることを見つけました。
whileループ変数iをインクリメントしていなかったのです。（なぜ途中まではACできたのか）
そのせいで無限ループに陥っていたと考えられます。

# 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;
        //ここにi++;と書くべきだった
    }
    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;
        //ここにi++;と書くべきだった
    }
}

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";
    }  
}

その間違いを修正することで通せました。