4 
    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 的问题。其他用户已经在堆栈流中询问过这个问题。[但这没有用，我想通过后缀 Array 来解决。]

如何使用后缀数组来解决这个问题？

直到现在我做了什么？

(1) 假设给定的字符串是 S。

我将字符串 S 与自身连接起来得到一个字符串 S'。

IE。S'=S+S。

(2).然后我在O(nlog n )时间内找到了S'的后缀数组。

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}。

我还计算了每个后缀的 LCPs b/w [虽然我不相信我会在这个问题中需要它]。

现在如何进一步进行。如何使用 SA 来获得所需的结果？

用一个非常*小的例子来解释会非常有效。

谢谢！！

4

3 回答 3

3

看来您应该在 SA 中取第一个后缀，该索引在 0 和 length(S) - 1 之间。

一些解释：S 的所有旋转都在 S' 后缀的开头，从 0 到 length(S) - 1 之间的位置。后缀数组按字典顺序保持后缀，所以你只需要选择从 S 的旋转开始的第一个.

于 2012-06-30T21:13:43.507 回答
2

如果您使用 O(n log n) 算法（按第一个字母排序，然后按前两个字母排序，然后按前四个字母排序，...），您可以制作一些修改后的后缀数组。

不要对字符串的后缀进行排序，但它是循环旋转。它应该是算法中的非常小的修改。A 然后你会直接得到想要的结果。

如果你仍然想使用你的方法，那么只需取第一个索引，它在 0 和 N 之间。

于 2012-06-30T22:41:42.013 回答
0

谢谢大家。vkorchagin 和 usamec 的答案对于大多数测试用例都是正确的，但它们不适用于以下测试用例（S="baabaa"）

S=咩咩；S'=巴巴巴巴巴；

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

取索引在 0 到 S.length()-1 之间的第一个后缀不适用于上述测试用例。如果我这样做，则结果为 4，但正确答案为 1。

所以我修改了答案，有点。

这就是我对上述答案所做或添加/修改的额外条件::

(1)我取了索引在 0 到 S.length()-1 之间的第一个后缀。

可以说它的索引是:=ExpectedIdx。

在上面的示例中，ExpectedIdx=4。

(2).现在 ExpectedIdx 可能是也可能不是答案。原因是后缀数组中的下一个后缀可能会产生相同的答案。

例子 ：：

取起始索引为 4 的后缀（ExpectedIdx），aabaabaa.，我们得到aabaab最小 Lexograhic 旋转字符串。

取下一个后缀aabaabaabaa。

我们还得到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;
}
于 2012-07-01T04:18:13.040 回答