最小辞书轮换使用后缀数组

本文介绍了最小辞书轮换使用后缀数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 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.