O（n）の文字列内の別個の部分文字列の数を数えることは可能ですか？

Question

長さがnの文字列sがある場合、O（n）内の別の部分文字列の数をsに数えることは可能ですか？

例

入力：abb

出力：5（'abb', 'ab', 'bb', 'a', 'b'）

は、私はいくつかの研究を行っているが、私はそのようにこの問題を解決するアルゴリズムを見つけることができないよう効率的な方法。私はO（n^2）アプローチが可能であることを知っていますが、より効率的なアルゴリズムがありますか？

それぞれの部分文字列を取得する必要はありません。違いがある場合は、別々の文字列の合計数だけを取得する必要があります。

Answer 1

あなたは線形時間で接尾辞木を構築するためにUkkonenのアルゴリズムを使用することができます。

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

Sのサブストリングの数はあなたが簡単に計算することができ、その後、トライ内の文字列のプレフィックスの数であります線形時間で。これは、すべてのノードの合計文字数です。ツリー内の

  /\     
      b a 
      | b 
      b b 

5文字なので、5つのストリング：

はたとえば、あなたの例のような接尾辞木を生成します。一意の各文字列は、別の文字の後ろのルートの末尾からのパスです：abb、ab、a、bb、b。したがって、文字列の数はツリー内の文字の数です。より正確には

：

• すべてのサブ文字列のいくつかの接尾辞の接頭辞です。
• すべての接尾辞はトライです。
• したがって、トライを通る部分文字列とパスの間には1対1の対応があります（トライの定義による）。各別個の空でないパスは、その最後の文字の後に異なる位置で終了
  • ;ためと
  • ツリー内の文字と非空のパス間の1-1の対応関係は、ありますそして
  • パスに各文字以下の位置は、OでO（N^2）の文字を含むツリーを構築することが可能になる可能性がどのように思っている人々のためNOTE

ユニークです（N）時間：

サフィックスツリーの表現にはトリックがあります。実際の文字列をツリーのノードに格納するのではなく、文字列にポインタを格納するだけで、 "abb"を含むノードには "abb"がなく、（0,3） - 2つの整数各ノードの文字列の長さに関係なく、接尾辞ツリーにはO（N）個のノードがあります。

Answer 2

LCP arrayを構成し、その合計を部分文字列の数（n（n + 1）/ 2）から減算します。