Just a week after publication of our article, Prof. Jan
Snellman of Stockholm University brought to our attention an
important reference we
overlooked, a 1993 article [Sha93] by Prof. Jeffrey O. Shallit of
the
University of
Waterloo. Our Theorem 8 (for the substring problem) should
now be thought of as generalizing
Shallit's Theorems 1 and 2 from alphabet size d=2 to
arbitrary d, with the added
observation that for d > 2
the
maximizing strings can be taken as prefixes
of a single infinite string, while for d=2 this is not possible.
We regret our oversight, perhaps arising from a failure to search on "factors" or "subwords" as well as "substrings", and we thank Prof. Shallit for his understanding.
Prof. Snellman also pointed out a technical error. In the statement of Theorem 8 (as is already correctly elucidated in its proof), k should not be the integer part of logd(n) but rather the integer such that dk+k-1 ≤ n < dk+1+(k+1)-1.
We are very grateful to Prof. Snellman for pointing out the
two errors,
and pleased that the electronic format of E-JC allows us to redress
them promptly.
Readers may also be interested in a recent paper by Svante Janson, Stefano Lonardi, and Wojciech Szpankowski [JLS03] and additional references cited therein.