发现没有后缀树和O（n）的字典序最小的串旋转 [英] find the lexicographically minimal string rotation without suffix tree and in O(n)

问题描述

如何找到该指数在一个圆形阵列，这样即形成从该指数开始字符串是第一个在字典顺序。

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.

有关例如：在圆阵ABCDEABCCDE 答案是6，因为从第六位元素的起始圆形串是第一位从圆形阵列的所有可能的字符串形成的字典。

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.

推荐答案

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

Theory A: If there are K occurrences of a letter X in a sequence of length N, there are at least two occurrences of X such that the distance between them is less than N/K.

查找最小信件并安排指向其所有出现在排序列表。叫它。

Find the min letter and arrange pointers to all of its occurrences in a sorted list. Call it A.

有关一个给定的R，找到的字母分钟A [1] + R，并过滤掉所有的量元件在A [1] + r为不等于min的指针。同时过滤掉所有的指针进行的研究[J]，使得A [D] = A [I] + R一段我。

For a given r, find min of letters at A[i]+r, and filter out all the pointers for which element at A[i]+r is not equal to min. Also filter out all the pointers A[j] such that A[j]=A[i]+r for some i.

您就要跑最多N / K倍以上声明，并在每次运行将花费最多O（K）的时间。因此，这种算法的复杂度为O（N）的

You will have to run the above statement at most N/K times and each run would cost at most O(K) time. Therefore, the complexity of this algorithm is O(N).

更详细的算法： 假设Z是圆形的名单，我们正在处理。

More detailed algorithm: Assume Z is the circular list we are dealing with.

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]

这篇关于发现没有后缀树和O（n）的字典序最小的串旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！