Maximizing integer sets intersection (with integer delta)

Question

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.

Answer 1

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.