Как алгоритм Дювала обрабатывает строки нечетной длины?

Question

Нахождение лексикографически минимального вращения строки - это хорошо известная проблема, для которой в 1983 г. Жан Пьер Дюваль предложил Жан Пьер Дюваль алгоритм линейного времени *. 1005 * Этот блог post, пожалуй, единственный общедоступный ресурс, который подробно описывает алгоритм.Однако алгоритмы Дюваля основаны на идее парных сравнений («дуэли»), и в блоге в качестве примера удобно использовать строку четной длины.

Как алгоритм работает для строк нечетной длины, гдеу последнего персонажа не будет соперника для поединка?

Answer 1

Один персонаж может получить « пока », где он выигрывает, не участвуя в «дуэли».Правильность алгоритма не зависит от конкретных поединков, которые вы проводите;учитывая любой два различных индекса i и j , вы всегда можете окончательно исключить, что один из них является начальным индексом лексикографически минимального поворота (если только оба являются начальными индексами идентичных лексикографически минимальных вращений, и в этом случае не имеет значения, какой из них вы отклоняете).Причиной проведения поединков в определенном порядке является производительность: чтобы получить асимптотически линейное время, убедившись, что половине поединков нужно сравнивать только один символ, половине остальных нужно сравнивать только два символа и т. Д. До последней дуэлинужно только сравнить половину длины строки.Но один нечетный символ здесь и там не меняет асимптотическую сложность, он просто делает математику (и реализацию) немного более сложной.Строка длиной 2 ⁿ + 1 по-прежнему требует меньше «дуэлей», чем одна длина 2 ^{n + 1} .

Answer 2

ОП здесь: я принял ответ Руаха, поскольку он касается моего вопроса, но я хотел дать свое собственное объяснение другим, которые могут наткнуться на этот пост, пытаясь понять алгоритм Дювала.

Проблема:

Лексикографически наименьшая круглая подстрока является проблемой нахождения вращение строки, имеющей самый низкий лексикографический порядок всех таких вращений. Например, лексикографически минимальный вращение "bbaaccaadd" будет "aaccaaddbb".

Решение:

Алгоритм времени O (n) был предложен Жаном Пьером Дювалом (1983).

С учетом двух индексов i и j алгоритм Дюваля сравнивает сегменты строки длиной j - i, начиная с i и j (называемые "дуэль" ). Если 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).

Сложность пространства также равна 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)
}