string - find the lexicographically minimal string rotation without suffix tree and in O(n)

Question

how to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order.

For Ex : in the circular array ABCDEABCCDE The answer is 6 because the circular string starting from the element A in the 6th position comes first in the dictionary formed from all the possible strings of the circular array.

Answer 1

理论 A：如果字母 X 在长度为 N 的序列中出现 K 次，则至少有两次出现 X，使得它们之间的距离小于 N/K。

找到最小字母并将指向其所有出现的指针排列在排序列表中。称它为A。

对于给定的 r，在 A[i]+r 处找到 min 个字母，并过滤掉 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) 的预期复杂度。