【AOJ ALDS1_4】C: Dictionary

問題

探索 3 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• mapを実装する問題
• STLのmap使えば簡単にできるんだけども, 「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を見つつ愚直に実装.
• ハッシュ関数は「ダブルハッシュをつかったオープンアドレス法」を利用した. オープンアドレス法は最初のハッシュ値の場所が埋まっていたら別のところを見つけて入れようねと言った感じ.
• オープンアドレス法の探索方法としては, ダブルハッシュの他にも線形探索したり平方探索ってのがあるみたい.

  コード

#include <iostream>

using namespace std;

#define M 1046527
#define h1(key) (key%M)
#define h2(key) (1+(key%(M-1)))
string s[M];

int getCode(char c){
  switch(c){
  case 'A':
    return 1;
    break;
  case 'C':
    return 2;
    break;
  case 'G':
    return 3;
    break;
  }
  return 4;
}

long long getKey(string in){
  long long sum = 0, p = 1;
  for(int i = 0 ; i < (int)in.size() ; i++){
    sum += (getCode(in[i]) * p);
    p *= 5;
  }
  return sum;
}

long long hash_f(long long key, int i){
  return (h1(key) + i * h2(key)) % M;
}

bool find(string in){
  long long key = getKey(in);
  
  for(int i=1;;i++){
    long long h = hash_f(key, i);
    if(s[h] == in) return true;
    else if(s[h].size() == 0) return false;
  }
}

void insert(string in){
  long long key = getKey(in);
  int i;
  for(i=1;;i++){
    long long h = hash_f(key, i); 
    if(s[h].size() == 0){
      s[h] = in;
      break;
    }
  }
}

int main(){
  int n;
  string command, in;
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    cin >> command >> in;
    if(command == "insert"){
      insert(in);
    }else{
      if(find(in)){
    cout << "yes" << endl;
      }else{
    cout << "no" << endl;
      }
    }
  }
    
}

参考

http://yamweb.comp.ae.keio.ac.jp/japanese/2011-A論/5-before-20111028.pdf