Duval 的算法如何处理奇数长度的字符串？

Question

找到 Lexicographically minimal string rotation is a well known problem, for which a linear time algorithm was proposed by Jean Pierre Duval in 1983. This 博客 post 可能是唯一公开可用的详细讨论算法的资源。不过Duval的算法是基于成对比较的思想("duels")，博客方便地以偶数长度的字符串为例

该算法如何适用于奇数长度的字符串，其中最后一个字符没有可与之竞争的字符？

Answer 1

一个角色可以获得“bye”，无需参与"duel"即可获胜。算法的正确性不依赖于你进行的具体决斗；给定 any 两个不同的索引 i 和 j，您总是可以最终排除其中之一是字典最小旋转的起始索引（除非 both 是 identical 字典最小旋转的起始索引，在这种情况下它不会'不管你拒绝哪个）。以特定顺序进行决斗的原因是性能：通过确保一半的决斗只需要比较一个角色，剩下的一半只需要比较两个角色，等等，直到最后一次决斗，从而获得渐近线性时间只需要比较字符串的一半长度。但是这里和那里的单个奇数字符不会改变渐近的复杂性，它只会使数学（和实现）稍微复杂一点。长度为 2ⁿ+1 的字符串仍然比长度为 2^{[=13= 的字符串需要更少的 "duels" ]n+1}.

Answer 2

OP 在这里：我接受了 ruakh 的回答，因为它与我的问题有关，但我想为可能偶然发现这个 post 试图理解 Duval 算法的其他人提供我自己的解释。

问题：

Lexicographically least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations. For example, the lexicographically minimal rotation of "bbaaccaadd" would be "aaccaaddbb".

解法：

Jean Pierre Duval (1983)提出了一种O(n)时间算法。

给定两个索引 i 和 j，Duval 的算法比较从 i 和 j 开始的长度为 j - i 的字符串段（称为 "duel")。如果index + j - i大于字符串的长度，则通过环绕形成段。

例如，考虑 s = "baabbaba"、i = 5 和 j = 7。由于 j - i = 2，因此从 i = 5 开始的第一段是 "ab"。从j = 7开始的第二段是通过回绕构造的，也是"ab"。如果字符串在字典序上是相等的，就像上面的例子，我们选择从 i 开始的那个作为获胜者，即 i = 5.

重复上述过程，直到我们有一个获胜者。如果输入字符串的长度为奇数，则在第一次迭代中不进行比较，最后一个字符获胜。

时间复杂度：

第一次迭代比较 n 个字符串，每个字符串的长度为 1（n/2 比较），第二次迭代可能比较 n/2 个长度为 2 的字符串（n/2 比较），依此类推，直到第 i 次迭代比较 2 个长度为 n/2 的字符串（n/2 比较）。由于每次获胜者人数减半，因此递归树的高度为 log(n)，因此给我们一个 O(n log(n)) 算法。对于小 n，这大约是 O(n)。

Space 复杂度也是 O(n)，因为在第一次迭代中，我们必须存储 n/2 个获胜者，第二次迭代 n/4 个获胜者，依此类推。（维基百科声称此算法使用常量 space，我不明白如何）。

这是一个 Scala 实现；随意转换为您喜欢的编程语言。

def lexicographicallyMinRotation(s: String): String = {
 @tailrec
 def duel(winners: Seq[Int]): String = {
   if (winners.size == 1) s"${s.slice(winners.head, s.length)}${s.take(winners.head)}"
   else {
     val newWinners: Seq[Int] = winners
       .sliding(2, 2)
       .map {
         case Seq(x, y) =>
           val range = y - x
           Seq(x, y)
             .map { i =>
               val segment = if (s.isDefinedAt(i + range - 1)) s.slice(i, i + range)
               else s"${s.slice(i, s.length)}${s.take(s.length - i)}"
               (i, segment)
             }
             .reduce((a, b) => if (a._2 <= b._2) a else b)
             ._1
         case xs => xs.head
       }
       .toSeq
     duel(newWinners)
   }
 }

 duel(s.indices)
}

Duval 的算法如何处理奇数长度的字符串？

How does Duval's algorithm handle odd-length strings?

string

algorithm

rotation

lexicographic