12
Для примера 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));
}
}
но, по моему пониманию он идет к N^2 мы можем сделать это быстрее, я ссылался на пронизывающий вопрос и была ссылка на суффикс-дерево http://allisons.org/ll/AlgDS/Tree/Suffix/, но он, похоже, не решает мою проблему .... вывод, который я получаю из дерева суффикса: {1: abcd 2: bcd 3: cd 4: d} Может ли кто-нибудь помочь мне найти самый быстрый способ сделать это? что-то вроде в линейном времени? Спасибо заранее .....
Вы не можете сделать это быстрее, чем O (n^2), чтобы даже указать начальную и конечную точки каждой возможной подстроки, так как существуют O (n^2) такие подстроки! Если вы хотите распечатать каждую подстроку в полном объеме (как вы сейчас делаете), тогда временная сложность переходит к O (n^3), поскольку для печати каждой подстроки требуется время, пропорциональное общей длине строки. –
Также обратите внимание, что пустая строка также является допустимой подстрокой. – Philip
Вы можете сделать это быстрее, если вы собираетесь запускать запрос по множеству подстрок, которые не «касаются» их всех. Их печать затрагивает все. Если вы хотите спросить, скажем, «какая самая длинная подстрока, которая появляется по крайней мере дважды» или «какая подстрока более чем k символов встречается наиболее часто», то вы можете сделать это без перечисления всех подстрок (с деревом суффиксов). – harold