兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

5.4 ハッシュ(自力版)

「ハッシュ」という言葉と、問題の図を参考に、自分なりに考えたのがこちら。「文字の種類は4つ」ということで、文字列を4進数とみなして、全部の組み合わせ分の bool 配列を持ち、insert 時に組み合わせを int 値にして、配列の index に読み替えてそこを true にする、という形式にしています。このあと解説を読みます。

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

using namespace std;

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

static inline int strToInt(const string& str) {
  int total = charToInt(str[0]);
  int cur;
  for (int i = 1; i < str.length(); i++) {
    cur = charToInt(str[i]);
    total += pow(4, i) * (1 + cur);
  }  
  return total;
}

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

  vector<bool> dictionary(static_cast<size_t>(pow(4, 12)) + 4, false);
  string command, str;

  for (int i = 0; i < n; i++) {
    cin >> command >> str;
    if (command[0] == 'i') {
      dictionary[strToInt(str)] = true;
    } else {
        cout << (dictionary[strToInt(str)] ? "yes" : "no") << endl;
    }
  }
  return 0;
}