The Interpol database contains a list of **N** stolen passport numbers. We have another list of **M** passport numbers to check if they are stolen or not.

**Input**

- The first line of the input contains an integer
**N**. - The next N lines contains the list of
**N**stolen passport numbers, one passport number per line. - The next line of the input contains an integer
**M**. - The next M lines contains the list of
**M**passport numbers, one passport number per line.

**Output**

Output the total number of stolen passports in the list of **M** passports.

**Constraints**

- Time Limit: 3s
- Memory Limit: 64MB
- 1≤N≤100,000
- 1≤M≤100,000
- Passport numbers are alphanumeric (combination of alphabetic and numeric characters) and are of length at most 15

**Problem Source: UTP Online Judge**

Let’s try solving this problem using hash table. Hash table is a data structure that can map **keys** to **value**.

For example, you have 9999 students’ ID with code from `0001`

to `9999`

and store it in an array, `A[]`

. Everyday, teachers will scan their ID if they’re present and you will receive an array of student list, say **Present**, like `{3478,0034,3203,0120,...,2840,0001}`

. If the principal wants you to print a list of students that are absent, your code would probably be:

**Pseudocode**

for i from 0001 to 9999 if not i in Present print i

This is simple and straightforward but the time complexity is not really good. First, you have to go through every element from `0001`

to `9999`

, . Then, to check if the element is in the list **Present**, you have to go through every element in that list, . So, your time complexity will be .

For hash table, the idea is as below:

**Pseudocode**

for i in Present A[i] = 1 for i from 0001 to 9999 if A[i] = 0 print i

It may look longer than the previous code, but it is much more efficient. First, we go through steps to record student who is present with `1`

in their corresponding index. Then, we scan through `A[]`

to print out the index of students with data `0`

, which means they are absent. This method results in time complexity of only.

Now, get back to the actual problem: Passport Checking. We first look at the overall solution involving hash table (`unordered_map`

in C++):

**C++**

#include <iostream> #include <string> #include <unordered_map> using namespace std; int main() { int N; cin >> N; unordered_map<string, int> stolen_map; unordered_map<string, int>::hasher fn = stolen_map.hash_function(); for (int i=0; i<N; i++){ string stolen; cin >> stolen; stolen_map[stolen] = fn(stolen); } int M; cin >> M; int cnt = 0; for (int i=0; i<M; i++){ string target; cin >> target; unordered_map<string, int>::const_iterator got = stolen_map.find(target); if (got != stolen_map.end()) cnt++; } cout << cnt << endl; return 0; }

Line `3`

:

#include <unordered_map>;

This allows us to use functions in `unordered_map`

.

Line `11`

:

unordered_map<string, int> stolen_map;

Create a hash table to map `string`

(stolen passports) to `int`

.

Line 13:

unordered_map<string, int>::hasher fn = stolen_map.hash_function();

Create a hash function (the method), `fn`

,to convert the `string`

(stolen passports) to `int`

and store it in `stolen_map`

.

Line `19`

:

stolen_map[stolen] = fn(stolen);

The stolen passport, type `string`

, is store with their value after entering the hash function `fn`

.

Line `30`

:

unordered_map<string, int>::const_iterator got = stolen_map.find(target);

To call for the `target`

value.

Line `31`

:

if (got != stolen_map.end())

If the `target`

value is searched.