Count of matched items in multiple sets

Question

I do apologize if this is a duplication. I did find a question that appears close to describing something of what I'm looking for, but I'm just not "seeing" the complete picture (maybe):

https://math.stackexchange.com/questions/591071/counting-matches-in-a-set - answered in comments without details for someone at my skill level; however, I am sure a simple mathematical expression (and possible term) exists for this concept, but mathematics is not my main area.

I have set A = {"Hey", "how", "are", "you"} and set B = {"Hey", "you"}, when compared, the result would be 2, because two elements in B are also in A. Further, if B = {"Hey", "are", "you", "John"}, when compared, the result would be 3, because while |A| and |B| is four, only three elements exist in common in both A and B.

How do I notate this concept? How do I describe this concept in plain language? And, if possible, what is the algorithmic representation of this concept?

Cheers.

Answer 1

Probably the easiest algorithm begins by sorting $A$ and $B$ into order. Then as long as neither $A$ nor $B$ is empty, repeat the following:

• If the first item of $A$ is equal to the first item of $B$, discard both, and increment a counter.
• Otherwise, discard the first item of $A$ or the first item of $B$, whichever comes first in sorted order.

When either $A$ or $B$ becomes empty, stop; the counter contains the number of common elements.

For large sets, it is more efficient to use a hash table.