Duval的算法如何处理奇数长度的字符串？ [英] How does Duval's algorithm handle odd-length strings?

问题描述

找到从字法上讲最小的字符串旋转是一个众所周知的问题，为此线性时间算法由Jean Pierre Duval在1983年提出。此博客文章可能是唯一详细讨论该算法的公开资源。但是，杜瓦尔（Duval）的算法基于成对比较（ duels）的概念，并且博客方便地使用偶数长度的字符串作为示例。

Finding the Lexicographically minimal string rotation is a well known problem, for which a linear time algorithm was proposed by Jean Pierre Duval in 1983. This blog post is probably the only publicly available resource that talks about the algorithm in detail. However, Duval's algorithms is based on the idea of pairwise comparisons ("duels"), and the blog conveniently uses an even-length string as an example.

算法适用于奇数长度的字符串，其中最后一个字符将没有与之竞争的决斗？

How does the algorithm work for odd-length strings, where the last character wouldn't have a competing one to duel with?

推荐答案

一个字符可以获取 再见，而无需参与决斗就可以获胜。算法的正确性不依赖于您执行的特定对决。给定 any 两个不同的索引 i 和 j ，您始终可以得出结论，其中之一是字典最小的起始索引旋转（除非都是是词典最小旋转的相同的起始索引，在这种情况下，您拒绝哪个旋转都没有关系）。按特定顺序执行决斗的原因是性能：通过确保一半的决斗只需要比较一个字符，其余的一半只需要比较两个字符来获得渐近线性时间，依此类推，直到最后一次决斗只需要比较字符串长度的一半即可。但是，这里和那里的单个奇数字符并没有改变渐近复杂性，它只是使数学（和实现）更加复杂。长度为2 ⁿ +1的字符串仍然需要比长度2 ^{n +1} 更少的决斗

One character can get a "bye", 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 2ⁿ+1 still requires fewer "duels" than one of length 2ⁿ⁺¹.

这篇关于Duval的算法如何处理奇数长度的字符串？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！