AIZU ONLINE JUDGE 4探索

4_A(線形探索)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    vector <int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    int m; cin >> m;
    vector <int> B(n);
    for (int i=0; i<m; i++) cin >> B[i];

    int cnt=0;
    for (int i=0; i<m; i++){
        int searchValue=B[i];
        for (int k=0; k<n; k++){
            if (searchValue==A[k]){
                cnt++;
                break; //breakすることで重複を防げる！
            }
        }
    }
    cout << cnt << endl;
}

4_B(二分探索)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    vector <int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    int m; cin >> m;
    vector <int> B(n);
    for (int i=0; i<m; i++) cin >> B[i];

    int cnt=0;


    for (int i=0; i<m; i++){
        int right=n-1;
        int left=0;
        while(left<=right){//見つからなければ,left>rightになるので"<="の条件でok!
            int middle=(left+right)/2;
            if (A[middle]==B[i]) {
                cnt++;
                break;
            } else if(A[middle]>B[i]){
                right=middle-1;
            } else{
                left=middle+1;
            }
        }
    }

    cout << cnt << endl;
}

4_C(ハッシュ)

#include <bits/stdc++.h>
using namespace std;

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

//文字から数値に変換
int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

//文字列から数値へ変換してkey(ハッシュ関数の入力値＆ハッシュ値)を同時生成
//AAAのキーは文字列"AAA"。これをハッシュ関数の引数として数値に変換したい。
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum; //ハッシュ値(数値変換出来上がり！)
}

//配列の添え字を決める(ハッシュ値が0~M-1になるように設定する)

//key=ハッシュ値(関数getKeyの返り値sumのこと！)
int h1(int key){ return key % M; }
int h2(int key){ return 1 + (key % (M-1)); }
//異なるkeyが同一のハッシュ値になっても大丈夫なオープンアドレス法
int hash(int key, int i){ return (h1(key)+i*h2(key))%M;}

int find(char str[]){
  long long key, i, h;
  key = getKey(str);
  for ( i = 0;; i++){
    h = hash(key, i);
    if( strcmp(H[h],str) == 0 ) return 1;
    else if ( strlen(H[h]) == 0 ) return 0;
  }
  return 0;
}

int insert(char str[]){
  long long key, i, h;
  key = getKey(str);
  for ( i = 0; ; i++ ){
    h = hash(key, i);
    if( strcmp(H[h],str) == 0 ) return 1;
    else if ( strlen(H[h]) == 0 ){
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}


int main(){
  int i, n, h;
  char str[L], com[9];
  for ( i = 0; i < M; i++ ) H[i][0] = '\0';
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s %s", com, str);

    if ( com[0] == 'i' ){
      insert(str);
    } else {
      if (find(str) ){
        printf("yes\n");
      } else {
        printf("no\n");
      }
    }
  }
  return 0;
}