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。这个问题该问题已经被其他用户询问堆流量。[但是，这并不像，我想通过后缀数组做有用的。]
如何做到使用后缀数组这个问题？
到现在为止我做了什么？
（1）可以说给定的字符串是S.
我串接带S自身得到一个字符串S”。
即。 S“= S + S。
（2）。然后，我发现S的”后缀数组中O（n日志n）的时间。
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。
此外，我计算出的液晶聚合物的B / W每一个后缀[虽然我没有信心，我需要它在这一问题。
现在， 如何进行further.How使用SA来获得想要的结果？
一个非常小的*示例说明将是十分有效的 。
谢谢！！
看来，你应该先后缀SA，其指数为0和长度（S） - 1之间。
一些解释：S的所有旋转是在S”后缀的0和长度（S）之间的位置开始 - 1.后缀阵列保持在字典序后缀，所以你只需要选择从S的旋转开头的第一个。
如果使用的是O（按首字母排序，然后通过前两个字母，然后由第4名，...）（N log n）的算法，可以使一点点修改后缀数组。
不要排序字符串的后缀，但它的循环圈。 它应该是在算法非常小的修改。 然后你会得到直接期望的结果。
如果你还是想用你的方法，然后只取其中为0和N之间的第一指标
感谢所有。无论答案通过vkorchagin和usamec对于大多数测试用例是正确的，但他们不会对下面的测试案例（S =“baabaa”）工作
S = baabaa; S“= baabaabaabaa;
Suffix| Suffix | Suffixes
Index | Length |
11 1 a
10 2 aa
7 5 aabaa
4 8 aabaabaa
1 11 aabaabaabaa
8 4 abaa
5 7 abaabaa
2 10 abaabaabaa
9 3 baa
6 6 baabaa
3 9 baabaabaa
0 12 baabaabaabaa
以第一后缀，其指数是S.length（）0 - 1之间的上述测试case.If我这样做，那么结果是4不起作用，但正确答案是1。
所以我修改了答案，有点。
这是我做过什么或者添加/修改一个额外的条件，上述答案::
（1）我把第一个后缀，其指数是S.length（）0 - 1之间。
可以说，它的指数为：= ExpectedIdx。
另外，在上述实施例ExpectedIdx = 4。
（2）。现在ExpectedIdx可以是或可以不是答案。 原因是在后缀数组的下标可以产生相同的答案。
例如::
以它的起始索引是4（ExpectedIdx），后缀aabaab AA，我们得到aabaab为最小Lexograhic旋转的字符串。
考虑下一步的后缀， aabaab aabaa。
我们也得到aabaab为最小Lexograhic旋转的字符串。
但前者要求4的移位而后者要求1的移位。 所以正确答案是1，不是4。
所以我用最长的公共前缀（LCP）的概念来检查的相似点和最后被录取了。 http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=756
编辑::这是伪代码 -
int ExpectedIdx,ExpectedSuffixNumber,ExpectedSuffixLength;
for(int i=0;i<strlen(str);++i)//str = Length of S'
{
suffixsize=strlen(str)-SA[i];
if(suffixsize>(Len/2))//Len/2:=Size of S
{
ExpectedIdx=SA[i];
ExpectedSuffixNumber=i;
ExpectedSuffixLength=suffixsize;
break;
}
}
//Now this ExpectediDx may or may not be the correct answer.
int finalans=ExpectedIdx;//Lets assume initially that ExpectedIdx is a correct/final answer.
for(int i=(ExpectedSuffixNumber+1);i<Len;++i)//Check the Next Suffix
{
if(LCP[i]>Len/2)//LCP[i]=Lingest common prefix of adjacent prefixes in a suffix Array.
{
if(SA[i]>finalans)
{
finalans=SA[i];
}
}
else
break;
}
