Duval的算法如何处理奇长字符串?

问题描述 投票:0回答:2

找到Lexicographically minimal string rotation是一个众所周知的问题,1983年Jean Pierre Duval提出了linear time algorithm.This博客文章可能是唯一公开讨论该算法的公开资源。然而,Duval的算法基于成对比较(“决斗”)的思想,博客方便地使用偶数长度的字符串作为例子。

该算法如何适用于奇数长度的字符串,其中最后一个字符不会与竞争的字符串决定?

string algorithm rotation lexicographic
2个回答
1
投票

一个角色可以得到一个“bye”,在没有参加“决斗”的情况下获胜。算法的正确性不依赖于您执行的特定决斗;给定任何两个不同的索引i和j,你总是可以最终排除它们中的一个是词典编码 - 最小旋转的起始索引(除非两者都是相同的词典编码 - 最小旋转的起始索引,在这种情况下它不会'无论你拒绝哪一个)。按特定顺序执行决斗的原因是性能:通过确保一半决斗只需要比较一个角色来获得渐近线性时间,其余一半只需要比较两个角色,依此类推,直到最后一次决斗只需要比较字符串长度的一半。但是这里和那里的单个奇数字符并没有改变渐近复杂度,它只是使数学(和实现)更复杂一点。长度为2n + 1的字符串仍然需要比长度为2n + 1的字符串更少的“决斗”。


0
投票

OP在这里:我接受了ruakh的答案,因为它与我的问题有关,但是我想为其他人提供我自己的解释,这些人可能偶然发现这篇文章试图理解杜瓦尔的算法。

问题:

按字典顺序排列的最小圆形子串是找到具有所有这种旋转的最低字典顺序的弦的旋转的问题。例如,“bbaaccaadd”的词典编码最小旋转将是“aaccaaddbb”。

解:

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

给定两个指数ij,Duval的算法比较从j - ii(称为“决斗”)开始的长度为j的字符串段。如果index + j - i大于字符串的长度,则通过环绕形成该段。

例如,考虑s =“baabbaba”,i = 5且j = 7.由于j-i = 2,从i = 5开始的第一段是“ab”。从j = 7开始的第二段是通过环绕构造的,并且也是“ab”。如果字符串在词典上是相等的,就像在上面的例子中一样,我们选择从i开始作为赢家的那个,即i = 5。

重复上述过程,直到我们有一个获胜者。如果输入字符串是奇数长度,则最后一个字符在第一次迭代中没有比较而获胜。

时间复杂度:

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

空间复杂度也是O(n),因为在第一次迭代中,我们必须存储n / 2个获胜者,第二次迭代n / 4个获胜者,等等。 (维基百科声称这个算法使用恒定的空间,我不明白如何)。

这是一个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)
}
© www.soinside.com 2019 - 2024. All rights reserved.