寻找按字典顺序最小化字符串旋转 https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation是一个众所周知的问题，对于这个问题线性时间算法 https://www.sciencedirect.com/science/article/pii/0196677483900172由让·皮埃尔·杜瓦尔于 1983 年提出。This https://ritukundu.wordpress.com/2016/10/07/algorithm-to-find-the-least-lexicographic-rotation-of-a-circular-string/博客文章可能是唯一详细讨论该算法的公开资源。然而，杜瓦尔的算法是基于成对比较（“决斗”）的思想，并且该博客方便地使用偶数长度字符串作为示例。
该算法如何处理奇数长度的字符串，其中最后一个字符没有与之竞争的字符？
One character can get a "bye https://en.wikipedia.org/wiki/Bye_(sports)", where it wins without participating in a "duel". The correctness of the algorithm does not rely on the specific duels that you perform; given any two distinct indices i and j, you can always conclusively rule out that one of them is the start-index of the lexicographically-minimal rotation (unless both are start-indices of identical lexicographically-minimal rotations, in which case it doesn't matter which one you reject). The reason to perform the duels in a specific order is performance: to get asymptotically linear time by ensuring that half the duels only need to compare one character, half of the rest only need to compare two characters, and so on, until the last duel only needs to compare half the length of the string. But a single odd character here and there doesn't change the asymptotic complexity, it just makes the math (and implementation) a little bit more complicated. A string of length 2n+1 still requires fewer "duels" than one of length 2n+1.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
