Maximizando a interseção de conjuntos inteiros (com delta inteiro)

Question

Existem dois conjuntos de inteiros com diferentes números de itens.

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

E há uma função de um único inteiro definido como

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

Isso é - eu acrescento delta inteiro para cada elemento do Y e então conte quantos inteiros iguais existem no X e o modificado Y.

E então o problema é encontrar delta que maximiza F(delta).

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

Existe algum nome "matemático" para tal tarefa e um algoritmo ideal para isso?Obviamente, posso usar força bruta aqui e enumerar todas as combinações possíveis - mas não funciona para n e m grandes.

Answer 1

Você pode calcular o sumset (bem, conjunto de diferenças) $X-Y$ usando técnicas padrão (Calculando Cardinalidade de Sumsets usando Convoluções e FFT).

Como otimização, sugiro primeiro substituir $X,Y$ com $X'=X\bmod p$, $Y'=Y \bmod p$ onde $p$ é pelo menos $n+m$ ou então.Então, enumerando os elementos do multiset $X'-Y'$ diminuindo a cardinalidade lhe dará bons candidatos para $\delta \bmodp$.O tempo de execução para calcular $X'-Y'$ vai ser $O((n+m)log(n+m))$, e se o valor máximo de $F(\delta)$ é suficientemente grande, espero que você consiga encontrar o valor correto para $\delta$ entre os primeiros candidatos.