Найти все возможные подстроки самым быстрым способом

Для строки 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));
    }
}

Но, насколько я понимаю, сложность связана с O(N^2). Можем ли мы сделать это быстрее? Я сослался на предыдущий вопрос, и была ссылка на дерево суффиксов, но это, похоже, не решило мою проблему. Вывод, который я получаю из дерева суффиксов, это

{
 1: abcd
 2: bcd
 3: cd
 4: d
}

Может ли кто-нибудь помочь мне найти самый быстрый способ сделать это? Что-то вроде линейного времени?

Ответы

Ответ 1

Вы не можете создавать строки O(N^2) быстрее, чем O(N^2). Это математическая невозможность. Даже если создание строки заняло одну инструкцию, это все равно вычисление O(N^2).

Оставляя сложность в стороне, я не думаю, что ваш код может быть улучшен каким-либо существенным способом.

Можем ли мы сделать это быстрее?

Вероятно, нет.

Оптимизация этого конкретного куска кода бесполезна. Поскольку вы записываете строки в стандартный вывод, фактическая производительность будет зависеть от накладных расходов на написание символов... и от того, что ОС делает с выводом.