最小辞书轮换使用后缀数组 [英] Minimum Lexicographic Rotation Using Suffix Array

问题描述

    Consider a string of length n (1 <= n <= 100000). 
    Determine its minimum lexicographic rotation. 
    For example, the rotations of the string "alabala" are:

    alabala

    labalaa

    abalaal

    balaala

    alaalab

    laalaba

    aalabal

    and the smallest among them is "aalabal".

这是由ACM ICPC问题2003。这个问题已经被问堆栈流由其他用户。[但那是不一样的，我希望通过后缀数组做有用的。]

This is the problem from ACM ICPC 2003 .This problem has already been asked in stack flow by some other user.[But that wasn't useful as , I want to do it by suffix Array.]

如何使用后缀数组做这个问题？

How to do this problem using the Suffix Array?

到现在为止我做了什么？

Till Now what I had done??

（1）可以说，在给定的字符串是S

(1) Lets say the given string is S.

我串联带S与自身得到一个字符串S'。

I concatenated the string S with itself to get a string S'.

IE浏览器。 S'= S + S。

ie. S'=S+S.

（2）。然后我发现的S在澳后缀阵列（n日志n）的时间。

(2).Then I found the suffix array of S' in O(nlog n )time.

For example:
    S=alabala
    S'=alabalaalabala

Suffix No. Index    Suffixes

0       13      a
1       6       aalabala
2       9       abala
3       2       abalaalabala
4       11      ala
5       4       alaalabala
6       7       alabala
7       0       alabalaalabala
8       10      bala
9       3       balaalabala
10      12      la
11      5       laalabala
12      8       labala
13      1       labalaalabala

所以，我计算出的后缀数组SA好，SA [] = {13,6,9,2,11,4,7,0,10,3,12,5,8,1}

So I calculated the suffix-array SA well ,SA[]={13,6,9,2,11,4,7,0,10,3,12,5,8,1}.

此外，我计算出的液晶聚合物/黑白每一个后缀[虽然我没有信心，我将要求它在这一问题。

Also I calculated the LCPs b/w every suffixes [Although i am not confident that I will require it in this problem].

现在如何进行further.How使用SA来获得想要的结果？

一个非常*小例子说明会相当的有效的。

Explanation with a very *small example will be quite effective.

谢谢！

推荐答案

看来你应该先后缀SA，这指数在0和长度（S） - 1

It seems that you should take first suffix in SA, which index is between 0 and length(S) - 1.

一些解释：•所有的旋转是在S'后缀由0和长度（S）位置的开始 - 1后缀阵列保持在字典序后缀，所以你只需要选择第一个它开始从的S旋转。

Some explanation: all rotations of S are in the beginning of S' suffixes from positions between 0 and length(S) - 1. Suffix array keeps suffixes in lexicographical order, so you just need to pick the first one which begins from rotation of S.

这篇关于最小辞书轮换使用后缀数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！