  The problem of constructing optimal factoring automata arises in the context
of unification factoring for the efficient execution of logic programs. Given
an ordered set of $n$ strings of length $m$, the problem is to construct a
trie-like tree structure of minimum size in which the leaves in left-to-right
order represent the input strings in the given order. Contrary to standard
tries, the order in which the characters of a string are encountered can be
different on different root-to-leaf paths. Dawson et al. [ACM Trans. Program.
Lang. Syst. 18(5):528--563, 1996] gave an algorithm that solves the problem in
time $O(n^2 m (n+m))$. In this paper, we present an improved algorithm with
running-time $O(n^2m)$.
