Binary string of length $2^n + n - 1$ that contains, as substrings, all strings of length $n$ There is a famous formula, used in the context of Sanskrit prosody, that is used to give names to all the binary strings of length 3. It goes something like yamaataaraajabaanasalagaa.
Read a as short syllable (1) and aa as long syllable (2). Then the names we get by taking three consecutive syllables at a time are as follows:
$$y=(1,2,2), m=(2,2,2), t=(2,2,1), r=(2,1,2),$$
$$j=(1,2,1), b=(2,1,1), n=(1,1,1), s=(1,1,2).$$
These names are used to describe meters in compact notation.
I want to get a generalized method for generating strings like these, i.e., instead of $3$, consider strings of length $n$ and find all strings of length $2^n + n - 1$, each of which contains, as substrings, all strings of length $n$.
 A: You could use the following method:


*

*Build a Fibonacci-style linear feedback shift register
of length $n$.
You will need a primitive polynomial
over $\mathbb{F}_2$ of degree $n$
to find suitable taps so the generated sequence has period $2^n-1$.

*Initialize the LFSR to a state where the output bit is $1$
and all other bits are zero.

*Clock the LFSR, then note the output bit.
Repeat until you have noted $2^n-1$ output bits.
The LFSR is now again at its inital state, so you have just noted a $1$.

*Append $n$ zeros.
The first $n-1$ zeros correspond to what you would get by clocking the LFSR,
and thus just complete the LFSR state readout.
The additional zero bit serves to provide the otherwise missing substring of
$n$ zeros.


I should add that the $2^n$-bit substrings of that sequence form
a De Bruijn sequence
which is a generalization of what you are asking for.
The first user mentioning that reference in this thread has been J.-E. Pin if I remember correctly.
Example $n=4$:
Initialize with $0001$ (output bit at the right).
XOR the output bit and the preceding bit together to form the
input bit. Together with the final zeros, this yields the $19$-bit string
$$0001001101011110000$$
which has $4$-bit substrings in hexadecimal notation:
$$\mathrm{1,2,4,9,3,6,D,A,5,B,7,F,E,C,8,0}$$
If we rename these to consonants such as
$$\mathrm{c,d,g,p,f,l,v,r,k,s,m,z,x,t,n,b}$$
and use short a for a $0$ bit and long aa for a $1$ bit,
this gives the naming sequence
cadagapaafalavaaraakasaamazaaxaataanaabacadaga.
Note that I have reused consonants at the end,
as the sequence can be considered to repeat after the ba.
