可能なすべての部分文字列を見つける方法

Question

たとえば、文字列A = "abcd" 答えは{a、ab、abc、abcd、b、bc、bcd、c、cd、d}にする必要がありますすべては、私は方法

for (int i = 0; i < A.length(); i++) { 
     for (int j = i+1; j <= A.length(); j++) { 
      System.out.println(A.substring(i,j)); 
     } 
    } 

しかし、それはN^2に行く私の理解によると、私たちが作ることができ、以下に使用したすべての部分文字列を検索するに

）...サブと呼ばれるかどうかが、私はそうと仮定していますされていますそれは速く私は過去の質問を参照してサフィックスツリーhttp://allisons.org/ll/AlgDS/Tree/Suffix/のリンクがあったが、それは私の問題を解決するようだ....サフィックスツリーから得る出力は{1：abcdです 2：bcd 3：cd 4：d} これを行う最速の方法を見つけるのに手伝ってください。線形時間のようなものですか？事前に感謝.....

Answer 1

O(N^2)文字列をO(N^2)時間より長く作成することはできません。それは数学的に不可能です。文字列を作成しても1つの命令があっても、それはまだO(N^2)です。

あなたのコードはどんな重要な方法でも改良することはできません。

---

私は実際のパフォーマンスは、出力ストリームに文字を書くのオーバーヘッドによって支配されようとしているので、このコードを最適化することは無益な活動が、あることを確認しなければならない...と何でもOSが出力しませんストリーム。