解説(というか答え)の写経版です。ハッシュ関数は、自力では思いつかないので、研究している人たちにおまかせするしかない感じです。
#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; }