# Algorithm for counting the number of strings at a particular edit distance

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?

• Is transposition considered an edit or only substitution, insertion and deletion? Oct 6, 2016 at 5:07
• Only insertion, deletion, and substitution are allowed. Oct 28, 2016 at 5:03

You can look into Levenshtein automaton. The main references are Fast String Correction with Levenshtein-Automata by Schulz and Mihov and Deciding word neighborhood with universal neighborhood automata by Mitankin, Mihov, and Schulz. There is an implementation called liblevenshtein which you can play with online here.

This algorithm gives you all words at distance at most $k$ from your string. So to get words that are at distance exactly $k$ you must remove the words at distance less than or equal to $k-1$.

• Thanks for the pointers, but this does not provide a polynomial time algorithm for the problem. Sep 15, 2016 at 17:01

I'll assume you are using an edit distance that can be computed in polynomial time and that the reverse of an edit is also an edit. Also, for any string there are only a polynomial number of possible edits. Then, reverse search will take time that is polynomial in the number of output strings, even if $k$ is an increasing function of $n$.

Define an order (say, lexicographic order) on the edits that can be made to a string. Call this with argument $s$:

procedure search(string t) Output $t$; if dist$(t,s) < k$ then for each string $u$ obtained by applying one edit to $t$ do if dist$(u,s)$=dist$(t,s)+1$ and $t$ is the result of applying the lexicographically least edit to $u$ then search($u$) endif endfor endif endprocedure

• Number of strings at a distance of $k$ can be larger than $(m-1)^k$, when you substitute $k$ tokens, so it is not polynomial in $k$ and $m$. Oct 28, 2016 at 5:06