Fast algorithm for finding mean minimum distances

Let $\xi_0,\dots,\xi_n$ be strings drawn from some finite alphabet. In this paper we describe an algorithm for finding mean minimum distances between strings $\xi_0,\dots,\xi_s$ for all $s\le n$. The complexity of the algorithm is $\mathcal O(nm)$, where $m$ is the length of strings.