Как найти число лексикографически минимального поворота строки?

Как найти количество лексикографически минимального поворота строки?

Например:

S = abab, N = 2
S = abca, N = 1
S = aaaa, N = 4

Пробовал алгоритм Дюваля, работает очень долго. Длина строки 100000000 символов.


string algorithm circular-buffer
person user3164559    schedule 09.01.2014    source источник
comment
Я не думаю, что вам нужно лексикографически минимальное вращение строки, но период периодической строки. stackoverflow.com/questions/8347812/   -  person Abhishek Bansal    schedule 15.01.2014
comment
Что вы имеете в виду под числом оборотов? У каждого поворота есть номер? Каков номер оборота? Вам не нужно общее количество вращений (rotationS - во множественном числе)?   -  person Tomas    schedule 17.01.2014
comment
Алгоритм Дюваля работает в O(N) с потребностью в памяти O(1). Если вам это кажется медленным, бросьте, быстрее не будет! Программе нужно хотя бы прочитать всю строку, что дает минимальное время O(N)!   -  person Tomas    schedule 17.01.2014
comment
Что вы называете очень долго? Как вы это реализовали? Используя какой язык? Правильно закодированный и оптимизированный алгоритм с линейным временем на 10^8 элементах должен занять несколько секунд.   -  person Yves Daoust    schedule 21.01.2014
comment
@Tomas O(N) не означает, что нет ничего, что могло бы быть быстрее. Может быть другой алгоритм со сложностью O (N) и в 100 раз более быстрым временем выполнения.   -  person kupsef    schedule 22.01.2014
comment
@kupsef только константой :) Да конечно знаю. Проблема ОП в том, что он помещает огромный объем данных в быстрый алгоритм и просто говорит, что это медленно. Что ему сказать :)   -  person Tomas    schedule 22.01.2014
comment
@Tomas Только константа, которая имеет значение на практике, когда вы сравниваете два алгоритма с одинаковой сложностью :) Я знаю, что проблема в огромном наборе данных, я просто хотел указать, что O (N) не означает самый быстрый :)   -  person kupsef    schedule 22.01.2014
comment
@kupsef ваш комментарий только теоретический. В этом случае вряд ли есть шанс, что ОП найдет что-то быстрее, чем Дюваль.   -  person Tomas    schedule 22.01.2014
comment
@Tomas Вы меня неправильно поняли, я просто хотел указать на ваш неверный вывод: O (N) --› самый быстрый   -  person kupsef    schedule 22.01.2014
comment
@ Томас Я очень хорошо тебя понял, но это только теоретическое обсуждение, как я писал в своем предыдущем комментарии, - не очень актуально для случая ОП. Послушайте, мы только что загромождали этот вопрос 6 комментариями о каком-то теоретическом обсуждении, я предлагаю сделать очистку комментариев и удалить эти комментарии.   -  person Tomas    schedule 22.01.2014

Ответы (1)


arrow_upward
4
arrow_downward

Легко -- просто определите минимальный период строки. Строка, периодическая в минимальном периоде K, будет давать идентичные (и, следовательно, лексикографически равные) строки ровно для N/K разных поворотов, поэтому каким бы ни был лексикографический минимум, он будет результатом N/K разных поворотов.

person Sneftel    schedule 09.01.2014
comment
Пробовал алгоритм Дюваля, работает очень долго. Длина строки 100000000 символов. - person user3164559; 11.01.2014
comment
Зачем вам алгоритм Дюваля? Ничто в определении числа наименьших перестановок не требует, чтобы вы нашли любую из них. - person Sneftel; 12.01.2014
comment
Тогда как я могу найти K? - person user3164559; 15.01.2014
comment
@user3164559: Ну, вы сказали N = 100000000 = 10^8. K должен быть делителем N. N = 10 ^ 8 = 2 ^ 8 * 5 ^ 8 имеет только 9 * 9 = 81 делитель. Не считая самого N, у нас остается 80 возможностей. Так почему бы просто не проверить все 80 возможных поворотов? Должно быть просто проверить каждую возможность за время O(N). - person Ruud Helderman; 15.01.2014