Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:
Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.
Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$
Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then $$r(x,y) = \sum_{t,s} x^t y^s \left|\left\{ (i,j) \in [n]\times[k] : i+k-j=t \wedge v_i + m - u_j =s \right\}\right|. $$
In particular, for $k \leq t \leq n$, the coefficient of $x^{t} y^m$ in $r(x,y)$ is $$\left|\left\{ (i,j) \in [n]\times[k] : i=j+t-k \wedge v_i = u_j\right\}\right| = k-d_H(u,v[t-k+1,t]).$$
Thus, the coefficients of $r(x,y)$ provide a lookup table for $d_H(u,v[t-k+1,t])$ for $k \leq t \leq n$.
So, given the coefficients of $r(x,y)$, we can easily solve the problem by picking the $t$ such that $x^{t}y^m$ has the largest coefficient:
Output: $f(u,v)+k=\mathrm{arg}\max_{k \leq t \leq n} \mathrm{coefficient}_{r(x,y)}(x^{t}y^m)$
So how fast is this algorithm? I claim it can be implemented in $O(nm \log (nm))$ time (assuming arithmetic operations with $O(\log (nm))$ bits of precision take constant time) using the Fast Fourier Transform.
The core of the problem is computing $r(x,y)=p(x,y)q(x,y)$, where the degree of $p(x,y)$ is at most $n$ in $x$ and $m$ in $y$ and the degree of $q(x,y)$ is at most $k$ in $x$ and $m$ in $y$.
We can first reduce it to univariate polynomial multiplication by defining $$p'(z) = p(z^{m+1},z) \qquad \text{and} \qquad q'(z)=q(z^{m+1},z),$$ computing $r'(z)=p'(z)q'(z)$, and then extracting $r(x,y)$ from the identity $r'(z)=r(z^{m+1},z)$.
I won't go through the FFT algorithm (even though it's one of my favourite algorithms), but the general idea is:
- Pick $\ell = O(nm)$ special points $w_1, \cdots, w_\ell \in \mathbb{C}$, namely $w_j=\exp(2\pi\sqrt{-1}j/\ell)$ and $\ell$ is a power of $2$ with $\ell > \mathrm{degree}(r'(z))=O(nm)$.
- Evaluate $p'(w_j)$ and $q'(w_j)$ for all $j \in [\ell]$ in $O(\ell \log \ell)$-time using a divide and conquer algorithm.
- Compute the values $r'(w_j)=p'(w_j)q'(w_j)$ for all $j$ in $O(\ell)$-time.
- Interpolate the coefficients of $r'(z)$ from the values $r'(w_j)$ in $O(\ell \log \ell)$-time using essentially the same divide and conquer algorithm.
The observation that makes the divide and conquer algorithm work is that we can write $p'(z) = p'_\text{even}(z^2) + z \cdot p'_\text{odd}(z^2)$, where $p'_\text{even}$ and $p'_\text{odd}$ have half the degree of $p'$. It then suffices to recursively evaluate $p'_\text{even}(w_{2j})$ and $p'_\text{odd}(w_{2j})$ for $j \in [\ell/2]$.
