3 
#include<iostream>
#include<string.h>
#include<utility>
#include<algorithm>

using namespace std;

struct xx
{
    string x;
    short int d;
    int lcp;
};

bool compare(const xx a,const xx b)
{
    return a.x<b.x;
}

int findlcp(string a,string b)
{
    int i=0,j=0,k=0;
    while(i<a.length() && j<b.length())
    {
        if(a[i]==b[j])
        {
            k++;
            i++;
            j++;
        }
        else
        {
            break;
        }
    }
    return k;
}

int main()
{   
    string a="banana";
    xx b[100];
    a=a+'$';
    int len=a.length();
    for(int i=0;i<len;i++)
    {
        b[i].x=a.substr(i);
        b[i].d=i+1;
    }
    sort(b,b+len,compare);
    for(int i=0;i<len;i++)
        cout<<b[i].x<<" "<<b[i].d<<endl;
    b[0].lcp=0;
    b[1].lcp=0;
    for(int i=2;i<len;i++)
    {
        b[i].lcp=findlcp(b[i].x,b[i-1].x);
    }
    for(int i=0;i<len;i++)
        cout<<b[i].d<<" "<<b[i].lcp<<endl;      
}

これは Suffix Arrayの実装です。ウィキペディアの記事の構成における私の質問は、最悪の場合 o(n) として与えられます

だから私の構築では：

  1. stl sort を使用して文字列のすべての接尾辞をソートしています。最悪の場合、これは少なくとも O(nlogn) になる可能性があります。したがって、ここでは O(n) 構造に違反しています。
  2. 2 つ目は、O(n) が与えられた最長共通プレフィックス配列の構築です。しかし、O(n^2) での実装だと思います。

したがって、最初のもの、つまりソート用

  • カウント ソートを使用すると、O(n) に減少する可能性があります。カウント ソートを使用すると、それは正しいですか?私の理解は正しいですか?私の理解が間違っている場合は教えてください

  • そして、O(n) 時間で LCP を見つける方法はありますか?

4

2 に答える 2

6

まず、あなたの2つの声明について：

1) stl ソートを使用して、文字列のすべてのサフィックスをソートしています。これは、最悪の場合、少なくとも O(nlogn) になる可能性があります。だからここで私はO（n）構造に違反しています。

ここの複雑さはstd::sortO(n log n) よりも悪いです。その理由は、O(n log n) は、O(n log n) 個の個別の比較があり、各比較が O(1) 時間で実行されると想定しているためです。アトミック アイテム (文字や整数など) ではなく、文字列を並べ替えているため、後者の仮定は間違っています。

メイン文字列の部分文字列である文字列項目の長さは O(n) であるため、ソート アルゴリズムの最悪の場合の複雑さは O(n 2 log n)であると言っても過言ではありません。

2) 2 つ目は、O(n) が与えられた最長共通プレフィックス配列の構築です。しかし、O(n^2) での実装だと思います。

はい、関数 n ==回を実行しているため、LCP 配列の構成は O(n 2 ) であり、関数は文字列のペアに対して O(min(len(x),len(y))) 時間を必要としますx、y。lcplenlcp

次に、あなたの質問について：

カウントソートを使用すると、O(n) に減少する可能性があります。カウントソートを使用すると正しいですか? 私の理解は正しいですか？私の理解が間違っている場合はお知らせください。

残念ながら、あなたの理解は間違っています。並べ替えのカウントは、O(1) 時間で、並べ替えたい各項目のアトミック キーにアクセスできる場合にのみ線形になります。繰り返しますが、アイテムは長さが O(n) 文字の文字列であるため、これは機能しません。

そして、O(n) 時間で LCP を見つける方法はありますか?

はい。DC アルゴリズム (別名スキュー アルゴリズム) を含むサフィックス配列計算の最近のアルゴリズムは、サフィックス配列と共に LCP 配列を計算するメソッドを提供し、それを O(n) 時間で実行します。

DC アルゴリズムのリファレンスは、Juha Kärkkäinen、Peter Sanders: Simple linear work suffix array construction、Automata、Languages and Programming Lecture Notes in Computer Science Volume 2719、2003、pp 943-955 (DOI 10.1007/3-540-45061-0_73) です。 ）。(ただし、線形時間でこれを実行できるアルゴリズムはこれだけではありません。)

この SO 投稿で言及されているオープンソースの実装も参照してください。現在の最先端のサフィックス配列構築アルゴリズムは何ですか? . そこで使用されているアルゴリズムの多くは、サフィックス配列の構築に加えて、線形時間 LCP 配列の構築を可能にします (ただし、すべての実装に実際にその実装が含まれているわけではありません。よくわかりません)。

Java の例に問題がない場合は、jSuffixArraysのコードも参照してください。これには、他のアルゴリズムの中でも、DC アルゴリズムの実装と、線形時間での LCP 配列の構築が含まれます。

于 2013-07-02T14:47:18.140 に答える