文字列が与えられた場合、 。 例 - abc サブストリングの一意のソートされたシーケンスは、 - a、ab、abc、b、bc、cです。したがって、ランクは3になります。 すべてのユニークな部分文字列を生成するよりも、ソート後にランクを見つけるよりも良い方法はありますか？私はこの質問のためにstlを設定し、タイムリミット超過を得ました。与えられた文字列文字列が与えられた場合、その文字列のユニークな部分文字列のソートされた（辞書編集的に）シーケンスの元の文字列のランクはどのようになるでしょうか
ため
まず接尾辞配列に元の文字列の位置を前に、その接尾辞配列
カウントユニークなストリングのためのlongest common prefix配列を作成します。例えば
、文字列は「ABABA」、その接尾辞配列sa[]、高さ配列height[i]=LCP(sa[i],sa[i-1])がされる場合：
| i | sa[i] | height[i] |
| ---- | ----- | --------- |
| 1 | A | 0 |
| 2 | ABA | 1 |
| 3 | ABABA | 3 |
| 4 | BABA | 0 |
| 5 | BA | 2 |
あなたはABABA前にあるすべての部分文字列が接尾辞に属し前で見ることができます接尾辞配列のABABAより大きい。たとえば、
Aは、sa[1]に属します。A,およびABAは、sa[2]に属する。しかし、最初の部分文字列が繰り返されます。A,,ABA,ABAB,ABABAはsa[3]に属する。しかし、最初の3つの部分文字列が繰り返されます。文字列全体が接尾辞配列で＃n位にランクされてあれば、答えは次のようになります。
\sum_{i=1}^{n} length(sa[i]) - height[i]
だから、「ABABA」の答えは1+3+5-1-3=5です。
この問題のソースコード全体をhereにすることができます。完全にはテストされていませんが、動作するはずです。
ビルドsuffix arrayは、与えられた文字列のsuffix arrayを構築し、
"ABABA"の回答はどうですか？それは5ですか？ – xmcp
はい、ランクは5になります。 –