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”.

これはACMICPC2003の問題です。この問題は、他のユーザーからスタックフローですでに質問されています。[しかし、それは役に立たなかったので、接尾辞配列で実行したいと思います。]

サフィックス配列を使用してこの問題を解決するにはどうすればよいですか？

今まで私がしたことは??

（1）与えられた文字列がSであるとしましょう。

文字列Sをそれ自体と連結して、文字列S'を取得しました。

すなわち。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}。

また、サフィックスごとにLCPを計算しました[この問題で必要になるとは確信していませんが]。

次に進む方法SAを使用して目的の結果を得る方法は？

非常に*小さな例での説明は非常に効果的です。

ありがとう！！

4

3 に答える 3

3

SAの最初のサフィックスを取得する必要があるようです。このサフィックスは0からlength（S）-1の間です。

説明：Sのすべての回転は、0からlength（S）-1までの位置からSの接尾辞の先頭にあります。接尾辞配列は辞書式順序で接尾辞を保持するため、Sの回転から始まる最初の接尾辞を選択する必要があります。 。

于 2012-06-30T21:13:43.507 に答える
2

O（n log n）アルゴリズム（最初の文字、次に最初の2文字、次に最初の4文字で並べ替え、...）を使用している場合は、少し変更された接尾辞配列を作成できます。

文字列のサフィックスを並べ替えないでください。ただし、循環回転です。これは、アルゴリズムの非常に小さな変更である必要があります。その後、あなたは直接望ましい結果を得るでしょう。

それでもメソッドを使用する場合は、0からNまでの最初のインデックスを取得します。

于 2012-06-30T22:41:42.013 に答える
0

おかげさまで、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

インデックスが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のシフトが必要です。したがって、正解は4ではなく1です。

そこで、Longest Common Prefix（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 に答える