@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 = "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",
}