Как сортировать вращение строк без использования матрицы

Question

Я хочу отсортировать повороты строки.
Например:

Для S = 'abaeb' поворот может быть 'baeba'

Мне нужно получить списокиндексы S, отсортированные в лексикографическом порядке.
В нашем примере: V = 02413.

Ответ должен исключать сортировку строк тривиальной матрицы.

Answer 1

Отредактировано: после Джастина Пила

Просто добавьте строку к себе bbaeb становится bbaebbbaeb (удобный прием для задач, связанных с вращением строки).
Найти суффиксный массив.
Пройдите через него и выберите только те значения, которые меньше длины оригинальной строки (5). Суффиксный массив для указанной выше строки

aeb  7
aebbbaeb  2
b  9
baeb  6
baebbbaeb 1
bbaeb 5
bbaebbbaeb 0
eb  8
ebbbaeb  3

S = 7 2 7 6 1 5 0 4 8 3

Теперь после прохождения Ans = 2 1 0 4 3

Изменить поверх

Вы можете решить это за O (n) временную сложность с использованием Суффиксный массив . В основном массив суффиксов для строки содержит индекс всех суффиксов строки в лексикографическом порядке.
Для строки abaeb суффикс в лексикографическом порядке:

abaeb (0)
aeb   (2)
b     (4) 
baeb  (1)
e     (3)

Итак, суффиксный массив S=02413

Код с временной сложностью O (n log ^ 2n) приведен по этой ссылке с подробным объяснением, и на следующей странице есть оптимизация для O (n) Если вы хотите, чтобы ваш код был простым, то ключевым условием является использование оператора сравнения, который уже отвечен. И если вас больше всего беспокоит эффективность, используйте конструкцию массива суффиксов o (n).

Answer 2

Как правило, для сортировки вам не нужно хранить все отсортированные элементы в памяти параллельно, вам нужно просто иметь возможность сравнить любую их пару.

Что я имею в виду, вы можете отсортировать индексы начала вращения строки (то есть 1 = 'baeba' и т. Д.) И предоставить метод сравнения, который будет сравнивать вращения на основе этого индекса.

Хотя сложность не лучше, чем nLog(n), код должен быть очень простым. Кроме того, цвет лица памяти близок к лучшему, что вы можете получить. Каким-то образом использование знания о том, что отсортированные элементы не являются случайными, может дать вам большую сложность (но в настоящее время я понятия не имею, как это сделать).

Answer 3

Если я правильно понимаю, у вас есть входная строка, и вы рассматриваете все повороты.Например, N поворотов строки длиной N будет, например:

rotations("abcd") -> ["abcd"*, "dabc", "cdab", "bcda"]

Вы хотите написать функцию компаратора compare(rotation1, rotation2), которая скажет, является ли rotation1 <или> или == rotation2, в контексте , что * исходное вращение было abcd или, альтернативно, иметь функцию key(rotation), которая эквивалентна вышеупомянутой функции компаратора.

Если этоневерно, уточните вопрос.=) Если это правильно, ваш ответ будет следующим:

original = 'abcd'

letterPositions = defaultdict(set)
for i,letter in enumerate(original):
    letterPositions[letter].add(i)

def numIndicesRotated(rotated):
    possibilities = set(range(len(original)))
    for i,letter in enumerate(rotated):
        possibilities &= {(j-i)%len(original) for j in letterPositions[letter]}
        if len(possibilities)==1: #optimization
            break                 #optimization

    if len(possibilities)==1:
        return possibilities.pop()
    else:
        raise Exception('not a rotation')

Обратите внимание, что вращения не могут быть чисто неупорядоченными, если у вас есть строка, которая имеет вращения, которые сами по себе, например, abcabc.

Тогда вы можете сделать что-то вроде sorted(myRotations, key=numIndicesRotated)