Some special strings

When playing with strings, either for fun, or to test and execute algorithms, it is always useful to have some way of creating artificial strings with specific properties. Here are two special strings that have specific properties that make them useful when reasoning about strings (e.g., to find worst case scenarios) or when trying to trip up the code you wrote.

Fibonacci strings

As you can imagine, they are strings inspired by the recursively defined Fibonacci series. Specifically, let us denote by $F_n$ the Fibonacci number of order $n$. By definition $F_n = F_{n-1} + F_{n-2}$ for all $n >= 3$. $F_1 = 1, F_2 = 1$. Similarly, we can define $FS_n = FS_{n-1} FS_{n-2}$ to be the Fibonacci string of order $n$, where the addition operation is replaced by the string concatenation operation. Also, $FS_1 = b, FS_2 = a$. It should be easy to see that the Fibonacci strings have lengths equal to the Fibonacci numbers of the same order. Here are some examples:

$FS_1 = b$ $FS_2 = a$ $FS_3 = ab$ $FS_4 = aba$ $FS_5 = abaab$

$\cdots$

De Bruijn strings

De Bruijn strings are a type of 'comprehensive' strings. Specifically, for a given alphabet $\Sigma$ and a length $k$, a de Bruijn string of order $k$ contains as substrings all strings of length $k$ over $\Sigma$. To see that such strings exist, are compact, and can be constructed we can build a simple graph (called a de Bruijn graph – more on that later). This graph contains as nodes all strings over $\Sigma$ of length $k-1$, and its edges connect nodes that overlap in a suffix-prefix fashion by exactly $k-2$ characters. Specifically, an edge exists for every pair of nodes $A, B$, where the corresponding strings have the form $x\alpha$, $\alpha y$ where $\alpha$ is a string of length $k-2$ and $x$ and $y$ are characters in $\Sigma$.

It is easy to see that such a graph is Eulerian (each node has equal in-degree and out-degree) and thus we can traverse it in such a way that every edge is seen exactly once. This traversal (which is not unique – rather one can have an exponential number of such traversals) spells out the de Bruijn string of order $k$.

De Bruijn graph of order 3 over the alphabet {a, b}. The nodes are all 2-letter strings and the edges represent all possible 1-letter overlaps between the nodes. An Eulerian tour of this graph generates a string that contains all 3-letter strings, i.e., the de Bruijn string of order 3.