2022/04/24 by Ruixi Luo, Luo, Ruixi, Taikun Zhu +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #68R15 #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2204.11213
openalex publication_date 2022/04/24 · openalex created_date 2022/04/28 · openalex updated_date 2026/07/28
We study the following rearrangement problem: Given n words, rearrange and concatenate them so that the obtained string is lexicographically smallest (or largest, respectively). We show that this problem reduces to sorting the given words so that their repeating strings are non-decreasing (or non-increasing, respectively), where the repeating string of a word A refers to the infinite string AAA…. Moreover, for fixed size alphabet Σ, we design an O(L) time sorting algorithm of the words (in the mentioned orders), where L denotes the total length of the input words. Hence we obtain an O(L) time algorithm for the rearrangement problem. Finally, we point out that comparing primitive words via comparing their repeating strings leads to a total order, which can further be extended to a total order on the finite words (or all words).