Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875559 | Theoretical Computer Science | 2018 | 9 Pages |
Abstract
We show an application of Lempel's recursive construction of De Bruijn words to the generation of binary words having many factor-rich prefixes. A binary word is said to be factor-rich iff it has the largest number of distinct factors among binary words with the same length. A linear de Bruijn word of rank n is a shortest word containing (as a factor) exactly once each binary word of length n. It is factor-rich and its length equals În=2n+nâ1. We construct for each n a binary linear de Bruijn word of rank n which is semi-perfect in the following sense: each of its prefixes of length m>Înâ1 is factor-rich. The number Înâ1 is the best possible (for n>2 there is no linear binary de Bruijn word with factor-rich prefix of length m=Înâ1). We show an efficient algorithm constructing compact description of binary semi-perfect de Bruijn words.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Damian Repke, Wojciech Rytter,