找到 Lexicographically minimal string rotation是一个众所周知的问题，为此 linear time algorithm由 Jean Pierre Duval 于 1983 年提出。This博客文章可能是唯一详细讨论该算法的公开可用资源。然而，Duval 的算法基于成对比较(“决斗”)的思想，并且该博客方便地使用偶数长度的字符串作为示例。
该算法如何适用于奇数长度的字符串，其中最后一个字符没有可与之竞争的字符？
最佳答案
一个角色可以获得“bye”，它在不参与“决斗”的情况下获胜。算法的正确性不依赖于你进行的具体决斗；给定 any 两个不同的索引 i 和 j，您总是可以最终排除其中之一是字典序最小的起始索引旋转(除非两者都是相同字典序最小旋转的起始索引，在这种情况下，您拒绝哪个并不重要)。以特定顺序进行决斗的原因是性能:通过确保一半的决斗只需要比较一个角色，剩下的一半只需要比较两个角色，等等，直到最后一次决斗，从而获得渐近线性时间只需要比较字符串的一半长度。但是这里和那里的单个奇数字符不会改变渐近的复杂性，它只会使数学(和实现)稍微复杂一点。长度为 2n+1 的字符串仍然比长度为 2n+1 的字符串需要更少的“决斗” .
关于string - Duval 的算法如何处理奇数长度的字符串？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55642656/