0

私は接尾辞配列と、2 つの接尾辞の最長共通接頭辞を計算するための使用について調べていました。

ソースは次のように述べています。

「2 つのサフィックス間の lcp は、アレイ上のそれらの間の隣接するサフィックスのすべてのペアの lcp の最小値です」

つまりlcp(x,y)=min{ lcp(x,x+1),lcp(x+1,x+2),.....,lcp(y-1,y) } 、x と y は、文字列の 2 つのサフィックスが始まる文字列の 2 つのインデックスです。

string の例のようなステートメントには納得できません"abca"。

lcp(1,4)=1（1ベースのインデックス作成を考慮）

しかし、上記の式を適用すると

lcp(1,4)=min{lcp(1,2),lcp(2,3),lcp(3,4)}

と私は思いますlcp(1,2)=0。

したがって、答え0は方程式に従う必要があります。

私はどこかで間違っていますか？

4

2 に答える 2

2

ソースが参照するインデックスは、文字列自体のインデックスではなく、ソートされたサフィックスのインデックスだと思います。

a
abca
bca
ca

したがって

lcp(1,2) = lcp(a, abca) = 1
lcp(1,4) = min(lcp(1,2), lcp(2,3), lcp(3,4)) = 0
于 2013-04-21T06:04:44.433 に答える
0

配列上でそれらの間の隣接するサフィックスのすべてのペアの lcp の最小値を計算するだけでは、2 つのサフィックスの LCP を見つけることはできません。

次の助けを借りて、任意の接尾辞 (i,j) の LCP を計算できます。

LCP(suffix i,suffix j)=LCP[RMQ(i + 1; j)]

また、 必ずしも等しいとは(i<j)限りませんのでご注意ください。RMQ はRange Minimum Query です。LCP (suff i,suff j)LCP (Suff j,suff i)

この論文の3ページ目。

Details:

ステップ 1: 最初に隣接/連続サフィックス ペアの LCP を計算します。

n= 文字列の長さ。

suffixArray[] はサフィックス配列です。

void calculateadjacentsuffixes(int n)
{
    for (int i=0; i<n; ++i) Rank[suffixArray[i]] = i;
    Height[0] = 0;
    for (int i=0, h=0; i<n; ++i)
    {
        if (Rank[i] > 0)
        {
            int j = suffixArray[Rank[i]-1];
            while (i + h < n && j + h < n && str[i+h] == str[j+h])
            {
                h++;
            }
            Height[Rank[i]] = h;
            if (h > 0) h--;
        }
    }
}

注: 高さ[i] = (接尾辞 i-1 、接尾辞 i) の LCP です。高さの配列には、隣接するサフィックスの LCP が含まれます。

ステップ2：

RMQ の概念を使用して、任意の 2 つのサフィックス i,j の LCP を計算します。RMQ 事前計算機能:

void preprocesses(int N)
{
    int i, j;

    //initialize M for the intervals with length 1
    for (i = 0; i < N; i++)
        M[i][0] = i;

    //compute values from smaller to bigger intervals
    for (j = 1; 1 << j <= N; j++)
    {
        for (i = 0; i + (1 << j) - 1 < N; i++)
        {
            if (Height[M[i][j - 1]] < Height[M[i + (1 << (j - 1))][j - 1]])
            {
                M[i][j] = M[i][j - 1];
            }
            else
            {
                M[i][j] = M[i + (1 << (j - 1))][j - 1];
            }
        }
    }
}

ステップ 3: 任意の 2 つのサフィックス i、j 間の LCP を計算する

int LCP(int i,int j)
{
    /*Make sure we send i<j always */
    /* By doing this ,it resolve following
    suppose ,we send LCP(5,4) then it converts it to LCP(4,5)
    */
    if(i>j)
        swap(i,j);

    /*conformation over*/

    if(i==j)
    {
        return (Length_of_str-suffixArray[i]);
    }
    else
    {
        return Height[RMQ(i+1,j)];
        //LCP(suffix i,suffix j)=LCPadj[RMQ(i + 1; j)] 
        //LCPadj=LCP of adjacent suffix =Height.
    }
}

RMQ 関数は次のとおりです。

int RMQ(int i,int j)
{
    int k=log((double)(j-i+1))/log((double)2);
    int vv= j-(1<<k)+1 ;
    if(Height[M[i][k]]<=Height[ M[vv][ k] ])
        return M[i][k];
    else
        return M[ vv ][ k];
}

RMQ については、Topcoder のチュートリアルを参照してください。

C++ での完全な実装は、私のブログで確認できます。

于 2013-04-21T06:34:18.207 に答える