Professor Zoltán Kása of Babes-Bolyai University has pointed out that all of our results for substrings were discovered by Professor Antal Iványi of Eötvös Loránd University in 1987 [Ivá87]. As in our Theorem 8, [Ivá87] used de Bruijn sequences to construct words of any alphabet size with the maximal number of distinct substrings, and showed that for alphabet size > 2 there is an infinite word whose n-prefixes suffice, and that for binary alphabets there is not. We are grateful to Kása and Iványi for their correspondence.
The connection between de Bruijn sequences and strings with maximally many distinct substrings is also used by Anisiu, Blázsik and Kása [ABK02] to calculate, for a given string length, the number of strings with maximally many distinct substrings.
Iványi's work [Ivá87] actually addresses "d-substrings", a notion introduced by Hunyadvári and Iványi [HI84] which interpolates between substrings and subsequences as d is varied. A d-substring of a string is a subsequence which can be obtained with gaps of at most d; for d=1 it is a substring and for d=infinity it is a subsequence. Kása [Kás98] also considers d-complexity (the number of d-substrings), focussing on the existence of a string with a given 1-complexity.
We note that if d is at least as large as the alphabet size, the string we construct having a maximum number of distinct subsequences has an equal number of distinct d-substrings, so our result generalizes immediately to d-complexity in that case. For d smaller than the alphabet size, a simple argument (obtained in a discussion with Don Coppersmith, and paralleling the recursion for Fibonacci numbers) shows that the maximum d-complexity of a string of length n is of asymptotic order Ln, where both L and the hidden constants depend on d.