Let $W$ be a cyclic word of length $n$ in a 2letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords (because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.
If you take a de Bruijn sequence of length $2^k$, then you have every length $k$ sequence precisely once. This implies that the number of subwords is maximal, since each subword of length $\geq k$ is determined uniquely by its prefix, and each subword of length $ < k$ occurs (with equal frequency). So this achieves the upper bound when $n=2^k$.

1$\begingroup$ A similar analysis applies for general n. If m is the smallest integer such that every subword of n of length m is unique, then the number of unique subwords total is at least n(nm+1). Thus m will always be at least floor(log n). But it should be possible to find a length n fragment of a Debruijn word which will achieve minimal m, as well as attain the largest number of distinct subwords of smaller length. Gerhard "Ask Me About System Design" Paseman, 2012.09.15 $\endgroup$ – Gerhard Paseman Sep 15 '12 at 17:20

1$\begingroup$ You can go the other way too. If you have a prescribed multiplicity for each word, you can form a corresponding directed (Eulerian) multigraph in an obvious generalization of the de Bruijn construction. Then you can use the matrixtree and BEST theorems to enumerate the sequences with these multiplicities. If you google "generalized de Bruijn" and restrict to site:mathoverflow.net you'll find one or two posts of mine on this topic. $\endgroup$ – Steve Huntsman Sep 15 '12 at 20:41

1$\begingroup$ Here is a nice paper on subword complexity that gives the same answer: csd.uwo.ca/faculty/ilie/IJFCS04.pdf . $\endgroup$ – Mark Sapir Sep 16 '12 at 12:14