既存の文字列のすべての部分文字列を決定する最も速い方法

Question

文字列が"Hey"であるとします。私はとして可能な限り速いこの文字列に存在する文字のすべての組み合わせを決定したいと思います。得られたアルゴリズムは、これを生成する必要があります。それがサブストリングとして文字列内に存在しないないため

H, e, y, He, ey, Hey 

アルゴリズムはないストリング"Hy"を生成しなければなりません。

Answer 1

は、これらの部分文字列のO(n^2)があり、長さ[1,n]のため、任意のアルゴリズムは、を生成するためにそれらのすべてがO(n^2) * O(n) = O(n^3)次のようになります。

（*）最後にEDIT2を参照してください - 文字列の実装に依存します - 複雑さはO(n^2)からO(n^3)

に変化させることができる擬似コード：

result <- {} #result is a set if dupes should be terminated, otherwise - it is a multiset. 
for i from 0 to s.length: 
    for j from i+1 to s.length: 
     result.add(s.substring(i,j)) 
return result 

注ただし、目

class MyIterator: 
    String s 
    int i,j 
    MyIterator(String s): 
    this.s = s 
    i = 0 
    j = 0 
    next(): 
    j = j + 1 
    if (j >= s.length): 
    i = i + 1 
    j = i + 1 
    if (i >= s.length): 
     throw exception 
    return s.substring(i,j) 

イテレータを作成することがO(1)であることに注意してください、そして各反復：あなたは、いくつかのイテレータを作成することにより、「不正行為」とその場で部分文字列を生成しないことが可能で、それはこのような何か[擬似コードを]になりますO(n)ですが、実際にすべての要素を生成するにはO(n^2)個のステップが必要です。したがって、複雑さは全体的にはO(n^3)のままですが、アプリケーションの待ち時間は短くなります。

EDIT：
私は、あなたが変数の長さの文字列を生成する必要があるため、複雑でO(n^3)あり、そのうちのいくつかが長いことがO(n^2)が間違っていると主張し、複雑さをeditted。生成されたサブストリングの少なくとも半分の長さn/2であろう - こうして総複雑性はEDIT2 Theta(n^3)

ある： - 文字列の実装に依存
いくつかのケースでは、それは実際O(n^2)することができます。例えば、Javaで - それは、単一のchar[]を使用し、唯一のoffsetとlengthで「演じる」 - Javaでて - それは、すべてのサブ以来、O(n^3)ある - サブストリングを作成することがCでO(1)
あるので、作成は、実際にO(n^2)です異なるchar[]にコピーする必要があります。

Answer 2

phpでnグラムの実装を確認してください。あなたの例の文字列で

：ねえ

H、E、Yユニグラムある

HE、EYはバイグラム

あるHEY、なぜそれが高速であることが必要トライグラム