想定解 : 二重ループを用いて実装する

それぞれの \(i = 1, 2, \dots, N\) について、\(j = 1, 2, \dots, M\) を全て試し、\(S_i\) の末尾 \(3\) 文字が \(T_j\) と一致するかどうかを判定することで正解することができます。

変数 count を 0 で初期化し、\(i = 1, 2, \dots, N\) それぞれに対して、以下の処理を行います。

1. 真偽値変数 found を false で初期化する。これは条件を満たす \(j\) が見つかったかどうかを表す。
2. \(j = 1, 2, \dots, M\) に対して、以下の処理を行う。
   • \(S_i\) の末尾 \(3\) 文字が \(T_j\) と一致しているなら、found に true を代入する。
3. found の値が true なら count の値を 1 増やす。

文字列 S の末尾 \(3\) 文字を得る方法は言語に応じて様々です。C++ なら S.substr(S.size() - 3) (S.size() == 6 なので S.substr(3) と等価) とし、Python なら S[-3:] とすればよいです。

実装例 (C++)

#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];
    }
    for (int j = 0; j < m; ++j) {
        cin >> t[j];
    }
    int answer = 0;
    for (int i = 0; i < n; ++i) {
        string suffix = s[i].substr(3);
        bool match = false;
        for (int j = 0; j < m; ++j) {
            if (suffix == t[j]) {
                match = true;
            }
        }
        if (match) {
            answer += 1;
        }
    }
    cout << answer << '\n';
    return 0;
}

実装例 (Python)

n, m = map(int, input().split())
s = [input() for _ in range(n)]
t = [input() for _ in range(m)]
answer = 0
for i in range(n):
  found = False
  for j in range(m):
    if s[i][-3:] == t[j]:
      found = True
  if found:
    answer += 1
print(answer)

別解 1 : 二分探索で \(T_j\) を見つける

こちらは少し高度な内容です。\(T_1, T_2, \dots, T_M\) を辞書順で昇順に並べ替えておくと、これらの中に指定された文字列が存在するかどうかを \(O(\log M)\) で検索することができます。制約が \(1 \leq N, M \leq 2\times 10^5\) と大きくなった場合、想定解では実行時間制限に間に合いませんが、この方法なら余裕を持って間に合います。

実装例 (C++)

#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];
    }
    for (int j = 0; j < m; ++j) {
        cin >> t[j];
    }
    sort(begin(t), end(t));
    int answer = 0;
    for (int i = 0; i < n; ++i) {
        if (binary_search(begin(t), end(t), s[i].substr(3))) {
            answer += 1;
        }
    }
    cout << answer << '\n';
    return 0;
}

別解 2 : 入力の特性を利用する

\(S_i\) は \(0\) 以上 \(10^6\) 未満の整数に対応し、\(T_j\) は \(0\) 以上 \(10^3\) 未満の整数に対応しています。\(S_i\) が表す整数を \(S_i'\)、\(T_j\) が表す整数を \(T_j'\) とおくと、\(S_i\) の末尾 \(3\) 文字が \(T_j\) に一致することは \(S_i'\) を \(10^3\) で割ったあまりが\(T_j'\) に等しいことと同値です。よって、\(k = 0, 1, \dots, 10^3 - 1\) に対し、\(T_j' = k\) となる \(j\) が存在するかどうかを求めておくことで、各 \(i\) に対し条件を満たす \(j\) が存在するかどうかを定数時間で求めることができます。

実装例 (C++)

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n);
    array<bool, 1000> exist = {};
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    for (int j = 0; j < m; ++j) {
        int t;
        cin >> t;
        exist[t] = true;
    }
    int answer = 0;
    for (int i = 0; i < n; ++i) {
        if (exist[s[i] % 1000]) {
            answer += 1;
        }
    }
    cout << answer << '\n';
    return 0;
}