论文标题
字符串重排不平等和原始单词之间的总顺序
String Rearrangement Inequalities and a Total Order Between Primitive Words
论文作者
论文摘要
我们研究以下重排问题：给定$ n $单词，重新排列和连接，以使所获得的字符串在词典上分别是最小（或最大）。我们表明，这个问题减少了对给定单词进行排序，因此它们的重复字符串是不折叠的（或分别为非增加的），其中一个单词$ a $的重复字符串是指无限字符串$ aaa \ ldots $。此外，对于固定尺寸的字母$σ$，我们设计了一个$ o（l）$ time排序单词的算法（在上述订单中），其中$ l $表示输入单词的总长度。因此，我们为重排问题获得了$ O（l）$时间算法。最后，我们指出，比较原始单词通过比较其重复字符串会导致总顺序，这可以进一步扩展到有限单词（或所有单词）上的总顺序。
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\ldots$. 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).
