Let α̃ be a length-L cyclic sequence of characters from a size-K alphabet 𝒜 such that for every positive integer m ≤ L, the number of occurrences of any length-m string on 𝒜 as a substring of α̃ is ⌊ L / K^m ⌋ or ⌈ L / K^m ⌉. When L = K^N for any positive integer N, α̃ is a de Bruijn sequence of order N, and when L ≠ K^N, α̃ shares many properties with de Bruijn sequences. We describe an algorithm that outputs some α̃ for any combination of K ≥ 2 and L ≥ 1 in O(L) time using O(L log K) space. This algorithm extends Lempel’s recursive construction of a binary de Bruijn sequence. An implementation written in Python is available at https://github.com/nelloreward/pkl.
@InProceedings{nellore_et_al:LIPIcs.CPM.2022.9, author = {Nellore, Abhinav and Ward, Rachel}, title = {{Arbitrary-Length Analogs to de Bruijn Sequences}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {9:1--9:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.9}, URN = {urn:nbn:de:0030-drops-161361}, doi = {10.4230/LIPIcs.CPM.2022.9}, annote = {Keywords: de Bruijn sequence, de Bruijn word, Lempel’s D-morphism, Lempel’s homomorphism} }
Feedback for Dagstuhl Publishing