3

サフィックス配列からLCPを構築するためのこのコードがどのように機能するかを誰かが説明できますか? ランクisuffixArr[]のサフィックスの文字列内のインデックスの値を保持するような配列です。 suffixArr[i]

 void LCPconstruct()
{
    int i,C[1001],l;
    C[suffixArr[0]] = n;


    for(i=1;i<n;i++)
    C[suffixArr[i]] = suffixArr[i-1];

    l = 0;

   for(i=0;i<n;i++)
   {
    if(C[i]==n)
        LCPadj[i] = 0;
    else
    {
        while(i+l<n && C[i]+l<n && s[i+l] == s[C[i]+l])
            l++;
        LCPadj[i] = l;

        l = max(l-1,0);
    }
  }

  for(i=0;i<n;i++)
     cout<<LCPadj[suffixArr[i]]<<"\n";


}
4

1 に答える 1

8

まず、アルゴリズムはサフィックスを元の順序、つまり入力文字列に現れる順序で処理することを理解することが重要です。辞書順ではありません。

したがって、入力文字列が の場合、abxabc最初に、次にabxabc、というように考慮されます。bxabcxabc

この順序で考慮する接尾辞ごとに、辞書編集上の前身(*)である接尾辞の位置を決定します (したがって、ここでは、ここでのみ、辞書編集順序の概念を使用します)。最初の接尾辞abxabcの場合、辞書編集上の前身、つまり辞書編集上の接尾辞の順序でその直前に現れる接尾辞は ですabc。Cこれは、この目的のために特別に用意された配列内の O(1) ルックアップによって決定されます。

abxabc内側のループは、 と の文字をabc1 つずつ比較し、これら 2 つのサフィックスの最初の 2 文字が共通していることを判別します。これはコード内の変数lであり、接尾辞の LCP のエントリはabxabc2 でなければならないことを意味するため、 を設定しLCPadj[i] = lます。iここでは、接尾辞配列内の位置ではなく、入力文字列内の接尾辞の位置を参照することに注意してください。LCPadjLCP アレイも (まだ)そうではありません。これは補助データ構造です。

次に、次の文字列に進みますbxabc。再び、それがその辞書編集上の前任者であることを検出するために使用Cしbc、2 つが共有するプレフィックス文字の数を決定します。そして、ここに秘訣があります。これは、少なくとも前のステップ (つまり 2) から 1 を引いた数でなければなりません。なぜでしょうか? 現在検討している文字列bxabcはもちろん、以前に検討した文字abxabc列 ( ) の接尾辞であるため、その文字列の辞書編集上の前身 ( abc) も 1 文字短い接尾辞 (bc)、そしてその接尾辞も接尾辞配列のどこかにある必要があり、その接頭辞を現在考慮されている文字列から最初の文字を除いたものと共有する必要があります。さらに、現在考慮されている文字列に短く、辞書編集的に近い接尾辞は他にありません。辞書式ソートがどのように機能するかを考えると、後者は非常に論理的ですが、これの正式な証明もあります (たとえば、ここでの Kärkkäinen の講義の Lemma 5.10 ) 。

これが、ここでの主な原理の説明です。各変数の役割を完全に理解するために、コードについて注意すべき点がいくつかあります。

  • 説明したように、Cは補助配列 (n長さは整数) であり、入力文字列の各接尾辞について、辞書編集上の直前の接尾辞である他の接尾辞の位置を格納します。この配列は、左から右にではなく、(賢明なことに) 接尾辞配列を左から右にたどって構築されます。これにより、任意の文字列の直前の辞書編集上の先行を簡単に判別できるためです。位置で始まる接尾辞の直前の辞書編集上の先行suffixArr[i]もちろん位置に配置する必要がありますsuffixArr[i-1]。Cこれがどのように定義されているかをコードで確認してください。
  • 前述のようLCPadjに、サフィックス配列に現れる順序ではなく、入力文字列に現れる順序でサフィックスの LCP 値を保存します。これが、出力時に が左から右に出力されるのでLCPadjはなく、サフィックス配列を左から右に通過し、LCPadj[i]その順序で出力される理由です。これが当てはまることを確認します。

これが役立つことを願っています。そうでない場合はお知らせください。

(*)辞書編集上の前任者とは、辞書編集的に順序付けられた接尾辞のリスト内の接尾辞の直前の前任者、つまり、接尾辞配列内のすぐ左にある接尾辞を意味します。

于 2014-10-18T09:48:19.900 に答える