AtCoder ABC 236 C - Route Map (5Q, 灰色, 300 点)

set の練習問題！

• 問題へのリンク

問題概要

個の文字列 と、 個の文字列 が与えられる。

について、 の中に と一致するものがあるかどうかを判定せよ。

制約

• 
• 各文字列の長さは 10 以下

考えたこと

set 型のよい練習問題。

を格納する集合（C++ であれば set<string> 型）を用意しよう。

そして、 について、 が集合に含まれるかどうかを判定していけばよい。

計算量

C++ の set 型を用いた場合、文字列の最大長さを として、計算量は

• 集合を作る部分： 回挿入するので、計算量は
• 判定していく部分： 回判定するので、計算量は

よって、全体の計算量は と評価できる。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N), T(M);
    for (int i = 0; i < N; i++) cin >> S[i];

    set<string> se;
    for (int i = 0; i < M; i++) {
        cin >> T[i];
        se.insert(T[i]);
    }

    for (int i = 0; i < N; i++) {
        if (se.count(S[i])) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}