５．４ ハッシュ（解説版）

解説（というか答え）の写経版です。ハッシュ関数は、自力では思いつかないので、研究している人たちにおまかせするしかない感じです。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

static inline int charToInt(char c) {
  switch(c) {
  case 'A':
    return 1;
  case 'C':
    return 2;
  case 'G':
    return 3;
  case 'T':
    return 4;
  default:
    return 0;
  }  
}

static inline uint64_t getKey(const string& str) {
  uint64_t total = 0, p = 1;
  for (int i = 0; i < str.length(); i++) {
    total += p * (charToInt(str[i]));
    p *= 5;
  }  
  return total;
}

static const int M = 1046527;
static const int NUL = -1;
static const int L = 14;

static inline int h1(int key) {
  return key % M;
}

static inline int h2(int key) {
  return 1 + (key % (M - 1));
}

static vector<string> H(M);

static inline bool find(const string& str) {
  uint64_t key, h;
  key = getKey(str);
  for (int i = 0;; i++) {
    h = (h1(key) + i * h2(key)) % M;
    if (H[h] == str) {
      return true;
    } else if (H[h].size() == 0) {
      return false;
    }
  }
  return false;
}

static inline bool insert(const string& str) {
  uint64_t key, h;
  key = getKey(str);
  for (int i = 0;; i++) {
    h = (h1(key) + i * h2(key)) % M;
    if (H[h] == str) {
      return true;
    } else if (H[h].size() == 0) {
      H[h] = str;
      return false;
    }
  }
  return false;
}

int main() {
  int n, h;

  cin >> n;

  string str, com;
  for (int i = 0; i < n; i++) {
    cin >> com >> str;
    if (com[0] == 'i') {
      insert(str);
    } else {
      cout << (find(str) ? "yes" : "no") << endl;
    }
  }
  return 0;
}