Наименьшее лексикографическое вращение строки с использованием массивов суффиксов в O (n)

Я процитирую проблему от ACM 2003:

Рассмотрим строку длиной n (1 <= n <= 100000). Определите его минимальное лексикографическое вращение. Например, вращения строки «алабала»:

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

и самый маленький среди них - «аалабал».

Что касается решения - я знаю, что мне нужно создать суффиксный массив - и скажем, я могу сделать это в O (n). Мой вопрос по-прежнему таков: как найти наименьшее вращение в O (n)? (n = длина строки)

Я очень заинтересован в этой проблеме, и все же я так или иначе не понимаю решение. Меня больше интересует концепция и способ решения проблемы, а не конкретная реализация.

Примечание: минимальный поворот означает в том же порядке, что и в словаре английского языка - «dwor» перед «словом», потому что d перед w.

РЕДАКТИРОВАТЬ: строительство массива суффиксов занимает O (N)

ПОСЛЕДНИЕ РЕДАКТИРОВАТЬ: я думаю, что нашел решение !!! Что если я просто объединю две строки? Так что если строка «alabala», то новая строка будет «alabalaalabala», и теперь я просто сконструировал бы массив суффиксов этого (в O (2n) = O (n)) и получил бы первый суффикс? Я думаю, это может быть правильно. Что вы думаете? Спасибо!

Простой способ построить все повороты строки длины N состоит в том, чтобы связать строку с собой.

Тогда каждая подстрока N-длины этой строки 2N-длины является поворотом исходной строки.

Поиск «лексикографически минимальной» подстроки выполняется с помощью вашей O (N) -структуры дерева.

Я почти уверен, что информация, содержащаяся в массиве суффиксов, недостаточна, чтобы помочь вам добраться до O (n), но в лучшем случае может помочь вам в O (n log n). Рассмотрим это семейство суффиксов:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Вы создаете следующий суффикс, беря предыдущий суффикс (скажем, aba), добавляя следующий еще не использованный символ, а затем снова добавляя предыдущий суффикс (так что aba -> aba c aba).

Теперь рассмотрим эти строки (пробел добавлен для выделения, но не является частью строки):

ad abacaba
bd abacaba
cd abacaba

Для этих трех строк начало массива суффиксов будет выглядеть так:

a
aba
abacaba
(other suffixes)

Выглядит знакомо? Эти строки, конечно же, предназначены для создания этого массива суффиксов. Теперь, в зависимости от начальной буквы (a, b или c), «правильный» индекс (решение вашей проблемы) - это либо первый, второй или третий суффикс в приведенном выше списке.

Выбор первой буквы практически не влияет на массив суффиксов; в частности, это не влияет на порядок первых трех суффиксов в массиве суффиксов. Это означает, что у нас есть log n строк, для которых массив суффиксов очень похож, но «правильный» индекс сильно отличается.

Хотя у меня нет веских доказательств, это настоятельно рекомендует мне, чтобы у вас не было другого выбора, кроме как сравнить вращения, соответствующие этим первым трем индексам в массиве, для их лексикографического упорядочения, что, в свою очередь, означает, что вам потребуется по крайней мере O (n log n) время для этого (поскольку число альтернативных первых символов - в нашем случае 3 - равно log n, а сравнение двух строк занимает время O (n)).

Это не исключает возможности использования алгоритма O (n). Я просто сомневаюсь, что массив суффиксов поможет вам в достижении этого времени выполнения.

Наименьший поворот - это тот, который начинается с некоторого суффикса из массива суффиксов. Суффиксы лексикографически упорядочены. Это дает вам большой старт:

• вы знаете, что как только вы получите такое k, что вращение, начинающееся с суффикса k, будет меньше, чем вращение, начинающееся с суффикса k +1, все готово (начиная с первого);
• Вы можете сделать сравнение «вращение, начинающееся с суффикса k , меньше, чем вращение, начинающееся с суффикса k +1» в O (1), сравнивая длины суффиксов и, опционально, сравнивая один символ с другим символом.

РЕДАКТИРОВАТЬ: «один символ с другим символом» может не всегда быть таким, это может быть больше чем один символ, но в целом, вы не проверяете больше чем n символов в течение всего процесса поиска, поэтому это O (n).

Краткое доказательство: вы проверяете символы только тогда, когда суффикс k +1 длиннее суффикса k , и останавливаетесь и находите свое решение, если суффикс k +1 короче суффикса k (тогда вы знаете, что суффикс k - это тот, который вы искали). Таким образом, вы проверяете символы только в возрастающей (по длине) последовательности суффиксов. Поскольку вы проверяете только лишние символы, вы не можете исследовать более n символов.

EDIT2: Этот алгоритм основан на том факте, что «если в массиве суффиксов есть два соседних суффикса, а предыдущий короче последующего, предыдущий - префикс последующего». Если это не так, то извините.

РЕДАКТИРОВАТЬ3: Нет, это не держит. «abaaa» имеет суффикс таблицы «a», «aa», «aaa», «abaaa», «baaa». Но, возможно, это направление мысли может в конечном итоге привести к решению, просто некоторые детали должны быть более сложными. Основной вопрос заключается в том, можно ли каким-либо образом провести вышеупомянутое сравнение, изучив меньше символов, так что это всего O (n), что, как я считаю, возможно. Я просто не могу сказать, как, сейчас.

Проблема:

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

Решение:

Алгоритм AO (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 строки длина н / 2 (н / 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)
}

Я не вижу ничего лучше, чем O (N²).

Если у вас есть список из N целых чисел, вы можете выбрать наименьшее из O (N) сравнений.

Здесь у вас есть список из N строк размером N (их создание ничего не стоит, строка полностью определяется ее начальным индексом). Вы можете выбрать наименьшее из O (N) сравнений. Но каждое сравнение - это O (N) базовых операций. Таким образом, сложность O (N²).