Прочитав это, похоже, что они просто сбрасывали все подстроки 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) каждый).
Более быстрое решение, которое они описали в конце, использовало суффиксные деревья, дополненные суффиксными ссылками, чтобы ускорить поиск, используя тот факт, что каждый поиск был сформирован путем удаления первого символа последнего поиска и добавления некоторого нового символа.