Минимальное вращение с использованием массива суффиксов

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

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

and the smallest among them is “aalabal”.

Этот вопрос уже задавался в стеке, но я задаю его, поскольку нет четкого решения. До сих пор я добился следующего прогресса.
1. Возьмите S, соедините с reverse(S)..let P=S+reverse(S)
2.Создайте массив суффиксов вышеуказанной строки P

Теперь мой вопрос: если я выберу первую строку в массиве суффиксов size> strlen(S), тогда префикс размера strlen(S) этой строки будет минимальным поворотом данной строки S.

Верен ли мой вывод?


string algorithm suffix-array
person username_4567    schedule 03.11.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Нет, вообще это неправильно (если я правильно понимаю, что вы имеете в виду). Конечно, это работает нормально для вашего палиндромного ввода.

См. следующий вывод интерпретатора Python, где входные строки включают 'alabala' и 'alabatta'. (В выходных данных добавлено несколько пробелов и переносов строк.) Во втором разделе первая часть первого суффикса длиннее S недопустима, т. е. не является поворотом S. См. третий раздел, где описан работающий подход.

>>> s = 'alabala'; p = s + ''.join(reversed(s))
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aalabala', 'abala', 'abalaalabala', 'ala', 'alaalabala',
 'alabala', 'alabalaalabala', 'bala', 'balaalabala', 'la',
 'laalabala', 'labala', 'labalaalabala']

>>> s = 'alabatta'; p = s + ''.join(reversed(s))
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aattabala', 'abala', 'abattaattabala', 'ala', 'alabattaattabala',
 'attaattabala', 'attabala', 'bala', 'battaattabala', 'la',
 'labattaattabala', 'taattabala', 'tabala', 'ttaattabala', 'ttabala']

>>> s = 'alabatta'; p = s + s
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aalabatta', 'abatta', 'abattaalabatta', 'alabatta', 
 'alabattaalabatta', 'atta', 'attaalabatta', 'batta', 'battaalabatta',
 'labatta', 'labattaalabatta', 'ta', 'taalabatta', 'tta', 'ttaalabatta']
person James Waldby - jwpat7    schedule 03.11.2012