Imagine we have a set of integers $$$x_1$$$ < $$$x_2$$$ < $$$x_3$$$ < ... < $$$x_n$$$. And let $$$d$$$ = $$$x_n$$$ — $$$x_1$$$. The pairwise distance between $$$x_i$$$ and $$$x_j$$$ is simply $$$|x_i - x_j|$$$. We need to compute the set of the values of the list of all pairwise distances, i.e. find $$$S = $$$ { $$$a \, | \, \exists i, j: |x_i-x_j|=a$$$ }.
For example, if we have integers {$$$1, 3, 4, 6$$$}, the set of all pairwise distance values is {$$$1, 2, 3, 5$$$}, because $$$|3-4| = 1$$$, $$$|1-3| = 2$$$, $$$|1-4| = 3$$$, $$$|1-6| = 5$$$ and there is no pair with a distance $$$4$$$.
The naive algorithm is apparently $$$O(n^2) \le O(d^2)$$$, whereas the best possible algorithm is at least $$$O(d)$$$, since there can be at most $$$d$$$ possible integer distances.
I came up with a bitmask algorithm, that has around $$$d^2/64$$$ operations.
I wonder if there is an asymptotically faster algorithm? I have been struggling for long, but I could not find any.
For a given integers $$$a_1, \ldots, a_n$$$ create two polynomials:
$$$P(x) = x^{a_1} + x^{a_2} + \ldots + x^{a_n}$$$
$$$Q(x) = x^{-a_1} + x^{-a_2} + \ldots + x^{-a_n}$$$
Calculate $$$P \cdot Q$$$ using FFT in $$$O(d \log d)$$$. Coefficient $$$kx^t$$$ of the result means that there are exactly $$$k$$$ ways to choose $$$i, j$$$ s. t. $$$a_i - a_j = t$$$.
Thank you! I will try.
$$$Q$$$ is not a polynomial, easy fix $$$x^d \cdot Q(x)$$$ is a polynomial.
Auto comment: topic has been translated by DSP-friendly (original revision, translated revision, compare)
actual 954I - Yet Another String Matching Problem moment