2026-07-25T05:29:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16136 2024-03-06T10:56:39Z ddc:004 open_access

Arbitrary-Length Analogs to de Bruijn Sequences Nellore, Abhinav Ward, Rachel de Bruijn sequence de Bruijn word Lempel’s D-morphism Lempel’s homomorphism 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhinav Nellore and Rachel Ward 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.9 urn:nbn:de:0030-drops-161361 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode