Intended solution: use a double loop

For each \(i = 1, 2, \dots, N\), try all \(j = 1, 2, \dots, M\) and check if the last three characters of \(S_i\) coincide with \(T_j\).

Initialize the variable count with 0. For each \(i = 1, 2, \dots, N\), do the following:

1. Initialize a boolean variable found with false, representing whether conforming \(j\) has been found.
2. For each \(j = 1, 2, \dots, M\), do the following:
   • If the last three characters of \(S_i\) equals \(T_j\), let found be true.
3. If the value of found is true, add 1 to the value of count.

The way to obtain the last three characters of S varies depending on languages. In C++, use S.substr(S.size() - 3) (or equivalently S.substr(3) because S.size() == 6); in Python, use S[-3:].

Sample code (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;
}

Sample code (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)

Bonus 1: Use binary search to find \(T_j\)

This is a bit advanced topic. If you sort \(T_1, T_2, \dots, T_M\) in lexicographically ascending order, one can check if a desired string is contained in it in an \(O(\log M)\) time. If the constraints were as large as \(1 \leq N, M \leq 2\times 10^5\), the intended solution did not finish in the time limit, while this approach did.

Sample code (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;
}

Bonus 2: Use the property of the input

\(S_i\) corresponds with an integer between \(0\) (inclusive) and \(10^6\) (exclusive), and \(T_j\) between \(0\) (inclusive) and \(10^3\) (exclusive). Let \(S_i'\) be the integer represented by \(S_i\) and \(T_j'\) be that by \(T_j\); then the last three characters of \(S_i\) coincide with \(T_i\) if and only if the remainder when \(S_i'\) divided by \(10^3\) equals \(T_j'\). Thus, by checking for each \(k = 0, 1, \dots, 10^3 - 1\) if there is \(j\) such that \(T_j' = k\) to respond to each \(i\) about the existence of desired \(j\) in a constant time.

Sample code (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;
}