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

希望给出代码

//利用键值对，查询比较快，时间复杂度可以达到O(n)
#include<iostream>
#include<string>
#include<map>
using namespace std;
void query(string A[], int n, string B[], int m) {
    map<string, int>num_map;
    for (int i = 0; i < n;i++) {
        pair<string, int>value(A[i], 1);
        num_map.insert(value);
    }
    for (int i = 0; i < m; i++) {
        map<string, int>::iterator it = num_map.find(B[i]);
        if (it != num_map.end()) {
            cout << B[i] << endl;
        }
    }
}
int main() {
    string A[] = { "ABC", "CD","D" };
    string B[] = { "A","CD","BC","ABC" };
    query(A, 3, B, 4);
}

你题目的解答代码如下：

#include<iostream>
#include<string>
using namespace std;

void query(string A[], int n, string B[], int m)
{
    int i,j;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            if(A[j] == B[i])
            {
                cout << B[i] << endl;
                break;
            }
}

int main()
{
    string A[] = {"ABC", "CD", "D"};
    string B[] = {"A", "CD", "BC", "ABC"};
    query(A, 3, B, 4);
}

如有帮助，望采纳！谢谢!