文字列の部分文字列に関する統計を注文する

Question

私は長い文字列sのサイズがnで、整数がiである。私はsのi番目の部分文字列が辞書順で興味があります。

単純なアプローチは、sのすべての部分文字列のセットを作成し、そのセットのi次統計を取得することです。このアプローチは、時間がO(n^2)だが、すべての部分文字列のセットをsにすることは、あまりにもメモリを要する。

「メモリにやさしい」アプローチがありますか？ここで

Answer 1

部分文字列は、文字列の接尾辞の接頭辞です。 http://en.wikipedia.org/wiki/Suffix_arrayで参照されているアルゴリズムの1つを使用して、時刻O（n）に接尾辞のソートされたリストを得ることができます。 JuhaKärkkäinenとPeter Sanders（2003）に言及されているもの。 「単純な線形作業接尾辞配列構造が合理的に簡単です。

サフィックスのソートされたリストから、怠惰なマージスキームのいくつかの並べ替えはあなたのサブストリングのサフィックス=ソートされたリストの接頭辞のソートされたリストを取得する必要があります。

Answer 2

は、i番目の文字列の先頭文字得るための方法である：（迅速に生成することができます）上記の結果から、今

s = "robert" 

cumulative = 0 
for c,num in sorted((j,i+1) for i,j in enumerate(reversed(s))): 
    print c,num,cumulative 
    cumulative+=x 

b 4 0 
e 3 4 
o 5 7 
r 2 12 
r 6 14 
t 1 20 

を、あなたは私が間にある場合、その累積値から見ることができます0と4では、最初の文字として 'b'を使用する必要があります。 私が7と12の間にあった場合、最初の文字として「o」を使用します。

：私たちが注文したサブ文字列を見ることができます。この（7と12の間で、それらのすべてが「O」で始まることを確認）（12の排他7の包括的なインデックス0、で始まる）を確認するために

print sorted([s[a:b] for a in range(n+1) for b in range(a+1,n+2)]) 
['b', 'be', 'ber', 'bert', 'e', 'er', 'ert', 'o', 'ob', 'obe', 'ober', 'obert', 'r', 'r', 'ro', 'rob', 'robe', 'rober', 'robert', 'rt', 't'] 

今すぐこのテクニックを使用して、最初の文字を取得できます。 最初に文字を取得すると、累積値から過去の部分文字列の数がわかります。この累積値をiから減算することができます。ここでは、の最初の（前に選択した）文字以降の新しい文字列を見ています（最初の文字を除く）。 2番目の文字を取得するために同じテクニックを再度適用します（新しい文字列と新しいi値を使用）。

これはうまくいけばうまくいきます。がんばろう。