CLR cover
Previous problem

Problem 54: Sorting Suffixes of Thue-Morse Words

Next problem

Thue-Morse words with their special structure provide examples in which some algorithms running in linear time or more can be optimised to run in logarithmic time instead. The problem shows such an example related to the Suffix array of words.

The infinite Thue-Morse word results from the iteration of the Thue-Morse morphism $\mu$ from $\{\sa{0}, \sa{1}\}^*$ to itself defined by \[\cases{ \mu(\sa{0}) = \sa{01} &\cr \mu(\sa{1}) = \sa{10} &\cr } \]

The Thue-Morse word $\tau_n$ is $\mu^n(0)$, for a natural integer $n$. This type of description of Thue-Morse words is suitable to describe recursively the array $\SA_n$ that lists the starting positions of non-empty suffixes of $\tau_n$ sorted according to the lexicographic order of the suffixes.

Given integers $n$ and $k$, $0\leq k \lt n$, show how to compute $\SA_n[k]$ in time $O(n)$ for the word $\tau_n$ of length $2^n$.

References

  • J. Radoszewski and W. Rytter. On the structure of compacted subword graphs of Thue-Morse words and their applications. J. Discrete Algorithms, 11:15-24, 2012.