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

Для String 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
}

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


java performance substring algorithm time-complexity
person user2228588    schedule 31.03.2013    source источник
comment
Вы не можете сделать это быстрее, чем O (n ^ 2), чтобы даже перечислить начальную и конечную точки каждой возможной подстроки, поскольку таких подстрок O (n ^ 2)! Если вы хотите распечатать каждую подстроку полностью (как вы это делаете сейчас), тогда сложность времени возрастет до O (n ^ 3), поскольку для печати каждой подстроки требуется время, пропорциональное общей длине строки.   -  person j_random_hacker    schedule 31.03.2013
comment
Также обратите внимание, что пустая строка также является допустимой подстрокой.   -  person Philip    schedule 31.03.2013
comment
Ускорить это можно только в том случае, если вы собираетесь выполнить запрос по набору подстрок, который не касается их всех. Их печать затрагивает всех. Если вы хотите спросить, скажем, какая самая длинная подстрока встречается как минимум дважды или какая подстрока из более чем k символов встречается чаще всего, вы можете сделать это без перечисления всех подстрок (с помощью дерева суффиксов).   -  person harold    schedule 31.03.2013
comment
строку for (int j = i+1; j <= A.length(); j++) следует заменить на for (int j = i+1; j <= A.length() - i; j++)   -  person HojjatK    schedule 09.06.2019

Ответы (1)


arrow_upward
51
arrow_downward

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

Если отбросить сложность, я не думаю, что ваш код можно значительно улучшить.

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

Возможно нет.

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

person Stephen C    schedule 31.03.2013