Генерируйте все уникальные подстроки для данной строки
Учитывая строку s, что самый быстрый метод должен генерировать ряд всех его уникальных подстрок?
Пример: для str = "aba" мы добрались бы substrs={"a", "b", "ab", "ba", "aba"}.
Наивный алгоритм должен был бы пересечь все строковые генерирующиеся подстроки в длине 1..n в каждом повторении, уступая O(n^2) верхняя граница.
Лучшее связывается возможное?
(это - технически домашняя работа, таким образом только для указателей приветствуются также),
1 ответ
Много ответов, которые включают 2 для циклов и .substring () заявление O вызова (N^2) временная сложность. Однако важно отметить, что худший случай для .substring () вызов в Java (сообщение обновляют 6 в Java 7) является O (N). Таким образом путем добавления .substring () вызов в коде, порядок N увеличился одним.
Поэтому 2 для циклов и .substring () вызов в тех циклах равняется O (N^3) временная сложность.