Генерируйте все уникальные подстроки для данной строки
Учитывая строку s, что самый быстрый метод должен генерировать ряд всех его уникальных подстрок?
Пример: для str = "aba" мы добрались бы substrs={"a", "b", "ab", "ba", "aba"}.
Наивный алгоритм должен был бы пересечь все строковые генерирующиеся подстроки в длине 1..n в каждом повторении, уступая O(n^2) верхняя граница.
Лучшее связывается возможное?
(это - технически домашняя работа, таким образом только для указателей приветствуются также),
4 ответа
Как говорили другие плакаты, потенциально существует O (n ^ 2) подстрок для данной строки, поэтому их распечатка не может быть выполнена быстрее, чем это . Однако существует эффективное представление множества, которое может быть построено за линейное время: суффиксное дерево .
ну, поскольку потенциально существует n * (n + 1) / 2 разных подстрок (+1 для пустой подстроки), я сомневаюсь, что вы можете быть лучше, чем O (n * 2) (худший случай). Проще всего их сгенерировать и использовать какую-нибудь красивую таблицу поиска O (1) (например, хэш-карту) для исключения дубликатов сразу после их обнаружения.
Нет способа сделать это быстрее, чем O (n 2 ), потому что в строке всего O (n 2 ) подстрок, поэтому, если вам нужно сгенерировать их все , их количество будет n ( n + 1) / 2 в худшем случае, отсюда верхняя нижняя граница O (n 2 ) Ω (n 2 ).
Для большого ох ... Лучшее, что вы могли бы сделать, это O (n ^ 2)
Не нужно изобретать колесо, это не струны, а наборы, так что вам придется концепции и примените их к своей ситуации.
Алгоритмы