# Maximizing integer sets intersection (with integer delta)

There are two sets of integers with different numbers of items in them.

X= { x_0, x_1, ... x_n }, x_0 < x_1 < ... < x_n
Y= { y_0, y_1, ... y_m }, y_0 < y_1 < ... < y_m


And there is a function of a single integer defined as

F(delta) = CountOfItems( Intersection( X, { y_0+delta, y_1+delta, ... y_m+delta) ) )


That is - i add delta integer to every element of the Y and then count how many same integers are in the X and the modified Y.

And then the problem - find delta that maximizes F(delta).

max( F(delta) ), where delta is integer


Is there some "mathematical" name for such task and optimal algorithm for this? Obviously i can use brute-force here and enumerate all possible combination - but it does not work for big n and m.

You can compute the sumset (well, difference set) $$X-Y$$ using standard techniques (Computing Cardinality of Sumsets using Convolutions and FFT).
As an optimization, I suggest first replacing $$X,Y$$ with $$X'=X \bmod p$$, $$Y'=Y \bmod p$$ where $$p$$ is at least $$n+m$$ or so. Then, enumerating through the elements of the multiset $$X'-Y'$$ by decreasing cardinality will give you good candidates for $$\delta \bmod p$$. The running time to compute $$X'-Y'$$ will be $$O((n+m)\log (n+m))$$, and if the maximum value of $$F(\delta)$$ is sufficiently large, I expect you should be able to find the correct value for $$\delta$$ among the first few candidates.