Как BST используются в качестве словарей для поиска строк? - PullRequest
0 голосов
/ 19 июня 2019

ссылка: https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK/NODE39.HTM

В следующей задаче автор обсуждает использование BST в качестве словаря для подстрок длины-k.Может кто-нибудь объяснить, как он это делает в контексте проблем.

1 Ответ

0 голосов
/ 19 июня 2019

Прочитав это, похоже, что они просто сбрасывали все подстроки length-k в стандартный BST. Порядок элементов определяется с помощью лексикографического порядка (сравнивайте символы по одному за раз, пока не будет обнаружено несоответствие, а затем решите результат сравнения на основе того, какой символ строки сравнивается ниже, чем у другого).

Чтобы проверить, была ли новая строка длины 2k действительной, они запустили скользящее окно длины k над ней, проверяя, была ли каждая подстрока длины k в BST. Если нет, они могут отклонить строку длиной 2 КБ и перейти к следующему кандидату. Это займет время O (k 2 log n), где n - общее количество подстрок длины-k, так как каждый поиск BST занимает время O (k log n) (O (k) поиска подстрок , с каждым поиском удаляющих O (log n) сравнений со стоимостью O (k) каждый).

Более быстрое решение, которое они описали в конце, использовало суффиксные деревья, дополненные суффиксными ссылками, чтобы ускорить поиск, используя тот факт, что каждый поиск был сформирован путем удаления первого символа последнего поиска и добавления некоторого нового символа.

...