Query

题目描述
We have a set of strings (set A) and a set of queries (set B). Each query is to check whether a string exists in set A or not. If yes, output this string.
Your task is to implement the following function:

void query(string A[], int n, string B[], int m);
Here, n is the number of strings in set A, m is the number of strings in set B. 1<=n,m<=500,000.
Submit the function only.

输入描述
No input.

输出描述
Output the strings in set B which exist in set A. The output should follow the original order of the strings in set B.

提示
For example,
A[0]=“ABC”, A[1]=“CD”, A[2]=“D”
B[0] = “A”, B[1] =“CD”, B[2]=“BC”, B[3]=“ABC”,
then you should output:
CD
ABC
ZHC的答案

#include"query.h"
using namespace std;
#include<iostream>

int myhash(const string s,int n){
    int hash = 13;
    int i = 0 ;
    while(s[i]){
        hash += (int)(s[i]);  
        hash =(hash*13)%n;    
        ++i;
    }
    return hash%n;
}

void query(string A[], int n, string B[], int m){
    int N=2*n;
    string hash_A[N];
    for(int i = 0 ; i < n ; ++i){
        int key = myhash(A[i],N);
        if(hash_A[key] == "") hash_A[key]=A[i] ;
        else{
            int k = 0;
            while(hash_A[(key+k*k)%N]!=""){//平方探测法
                ++k;
            }
            hash_A[(key+k*k)%N]=A[i] ;
        }
    }
    for(int i = 0 ; i < m ; ++i){
        int key = myhash(B[i],N);
        int k = 0;
            while(hash_A[(key+k*k)%N]!= ""){
                if(B[i]==hash_A[(key+k*k)%N]){
                    cout<<B[i]<<endl;
                    break;
                }
                ++k;
            }
    }
}

Yizuodi的答案

#include <iostream>
using namespace std;

int get_hash(const string s,int n){
    int hash = 0;
    for(int i=0;i<s.size();++i){
        hash += s[i]-'A'+1;  
        hash = (hash*26)%n;
    }
    return hash%n;
}

void query(string A[], int n, string B[], int m){
    string hashtable[2*n];
    for(int i = 0 ; i < n ; ++i){
        int key = get_hash(A[i],2*n)%(2*n);
        if(hashtable[key].size() == 0){
            hashtable[key]=A[i];
        }
        else{
            int j = 0;
            while(hashtable[(key+j*j)%(2*n)].size() != 0){
                ++j;
            }
            hashtable[(key+j*j)%(2*n)]=A[i];
        }
    }
    for(int i = 0 ; i < m ; ++i){
        int key = get_hash(B[i],2*n)%(2*n);
        int j = 0;
            while(hashtable[(key+j*j)%(2*n)].size() != 0){
                if(B[i]==hashtable[(key+j*j)%(2*n)]){
                    cout<<B[i]<<endl;
                    break;
                }
                ++j;
            }
    }
}