@inproceedings{f9b2e411dbf647d087cbc00e22193aec,
title = "Arbitrary-Length Analogs to de Bruijn Sequences",
abstract = "Let αe be a length-L cyclic sequence of characters from a size-K alphabet A such that for every positive integer m ≤ L, the number of occurrences of any length-m string on A as a substring of αe is ⌊L/Km⌋ or ⌈L/Km⌉. When L = KN for any positive integer N, αe is a de Bruijn sequence of order N, and when L ≠ KN, αe shares many properties with de Bruijn sequences. We describe an algorithm that outputs some αe for any combination of K ≥ 2 and L ≥ 1 in O(L) time using O(Llog 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.",
keywords = "Lempel's D-morphism, Lempel's homomorphism, de Bruijn sequence, de Bruijn word",
author = "Abhinav Nellore and Rachel Ward",
note = "Funding Information: We thank Arie Israel, {\v S}t{\v e}p{\'a}n Holub, Joe Sawada, Jeffrey Shallit, and the anonymous reviewers for the 33rd Annual Symposium on Combinatorial Pattern Matching for their helpful feedback on various iterations of this manuscript. AN thanks the Oden Institute for Computational Engineering & Sciences at the University of Texas at Austin for hosting him as a visiting scholar as part of the J. Tinsley Oden Faculty Fellowship Research Program when the work contained here was initiated. Publisher Copyright: {\textcopyright} Abhinav Nellore and Rachel Ward; licensed under Creative Commons License CC-BY 4.0; 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 ; Conference date: 27-06-2022 Through 29-06-2022",
year = "2022",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.CPM.2022.9",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Hideo Bannai and Jan Holub",
booktitle = "33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022",
address = "Germany",
}