Tìm tất cả chuỗi con có thể theo cách nhanh nhất

Question

Ví dụ: Chuỗi A = "abcd" thì câu trả lời phải là {a, ab, abc, abcd, b, bc, bcd, c, cd, d} (Tôi không biết điều này tất cả đều được gọi là chuỗi con hay không nhưng tôi giả định như vậy ...)

để tìm tất cả các chuỗi con tôi đã sử dụng phương pháp

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

sau Tuy nhiên, theo hiểu biết của tôi nó đi đến N^2 chúng ta có thể làm nó nhanh hơn tôi tham khảo câu hỏi pervious và có liên kết cho cây hậu http://allisons.org/ll/AlgDS/Tree/Suffix/ nhưng nó không có vẻ để giải quyết vấn đề của tôi .... đầu ra mà tôi nhận được từ hậu tố cây là {1: abcd 2: bcd 3: cd 4: d} bất kỳ ai có thể giúp tôi tìm cách nhanh nhất để làm điều này không? cảm ơn trước .....

Answer 1

Bạn không thể tạo chuỗi O(N^2) tốt hơn thời gian O(N^2). Nó là một phép toán không thể. Ngay cả khi tạo một chuỗi có một chỉ lệnh, đó vẫn là một tính toán O(N^2).

Tôi không nghĩ rằng mã của bạn có thể được cải thiện theo bất kỳ cách nào đáng kể.

---

tôi nên quan sát rằng tối ưu hóa mã này là một hoạt động vô ích, vì hiệu suất thực tế sẽ được chi phối bởi các chi phí chung của văn bản cho nhân vật vào dòng đầu ra ... và bất cứ hệ điều hành thực hiện với sản lượng suối.