सबसे तेज़ तरीके से सभी संभावित सबस्ट्रिंग

Question

उदाहरण के लिए स्ट्रिंग ए = "एबीसीडी" तो उत्तर {ए, एबी, एबीसी, एबीसीडी, बी, बीसी, बीसीडी, सी, सीडी, डी} होना चाहिए (मुझे नहीं पता कि यह क्या है सब-स्ट्रिंग नहीं कहा जाता है या लेकिन मैं तो यह सोचते हैं रहा हूँ ...)

सब-स्ट्रिंग मैं का इस्तेमाल किया है विधि

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

निम्नलिखित जानने के लिए लेकिन मेरी समझ के अनुसार यह करने के लिए एन^2 हम कर सकते हैं चला जाता है यह तेज़ी से मैंने गंभीर सवाल उठाया और प्रत्यय पेड़ http://allisons.org/ll/AlgDS/Tree/Suffix/ के लिए लिंक था लेकिन यह मेरी समस्या को हल करने के लिए प्रतीत नहीं होता .... आउटपुट जो मुझे प्रत्यय पेड़ से मिलता है {1: abcd 2: बीसीडी 3: सीडी 4: डी} क्या कोई भी ऐसा करने के लिए सबसे तेज़ तरीका खोजने में मेरी सहायता कर सकता है? रैखिक समय की तरह कुछ? अग्रिम धन्यवाद .....

Answer 1

आप O(N^2) समय से बेहतर O(N^2) तारों को नहीं बना सकते हैं। यह एक गणितीय असंभवता है। एक स्ट्रिंग बनाने के बावजूद भी एक निर्देश ले लिया, यह अभी भी O(N^2) गणना है।

मुझे नहीं लगता कि आपके कोड को किसी भी महत्वपूर्ण तरीके से बेहतर किया जा सकता है।

---

मैं पालन करना चाहिए कि इस कोड के अनुकूलन एक व्यर्थ गतिविधि है, क्योंकि वास्तविक प्रदर्शन उत्पादन धारा को वर्ण लिखने की ओवरहेड्स का बोलबाला होने जा रही है ... और जो कुछ भी ओएस उत्पादन के साथ करता है धारा।