найти лексикографически минимальное вращение строки без дерева суффиксов и в O (n)

Question

найти индекс в круговом массиве, чтобы строка, которая формируется, начиная с этого индекса, сначала в лексикографическом порядке.

Для примера: в круговой массиве ABCDEABCCDE Ответ равен 6, потому что круговая строка, начинающаяся с элемента A в 6-й позиции, входит сначала в словарь, образованный из всех возможных строк круговой массива.

Answer 1

Теория A: Если в последовательности длины N есть K вхождений буквы X, то существует как минимум два вхождения X, так что расстояние между ними меньше N/K.

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

Для данного г найдите минимум букв в A [i] + r и отфильтруйте все указатели, для которых элемент в точке A [i] + r не равен min. Также отфильтруйте все указатели A [j] такие, что A [j] = A [i] + r для некоторого i.

Вам нужно будет выполнить вышеуказанное утверждение не более N/K раз, и каждый прогон будет стоить не более O (K). Поэтому сложность этого алгоритма O (N).

Подробный алгоритм: Предположим, что Z - это круговой список, с которым мы имеем дело.

def filter(A,Z,r): 
    t = min(Z[A[i]+r]) forall i 
    remove A[i] if Z[A[i]+r]!=t forall i 

    rmflag = [false if A[i]==A[j]+r else false for i in range(len(A)] //NOTE: This step can be done in O(len(A)) time since A is sorted 
    remove A[i] if rmflag[i] 

Answer 2

Step 1: find the min char, call it minChar 
Step 2: build list L0 = {i: string[i] == minChar, but string[i-1] != minChar} 
Step 3: if L0.size() == 1, return L0[0] 
step 3: 
     3.0 set k=0, let L = L0 
     3.1 k++ 
     3.2 BUild L1 = {i+1, i in L}. Build L = {i: string[i] is smallest for any k in L1} 
     3.3 If L.size() == 1, return L[0]-k. Otherwise goto 3.1 to repeat 

Это должно дать вам O (N) ожидается сложности.