As input we are given a string $s$ comprising $n$ tokens from a vocabulary of size $m$. We are asked to count the number of strings from the same vocabulary that are at a particular edit distance of $k$ away from $s$.

Is there an efficient algorithm in $n$, $m$, and $k$ for this problem?