Как реализовать поиск общих элементов двух массивов с помощью суффиксного дерева?

На входе у нас есть два возрастающих массива целых чисел: a[m], b[n].
Нужно найти количество одинаковых элементов: a[i] == b[j].
Поиск нужно реализовать с помощью суффиксного дерева, число действий должно быть порядка m + n.

Подскажите, как можно организовать такой поиск именно с помощью суффиксного дерева?
  • Вопрос задан
  • 551 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Для отсортированных массивов достаточно просто выполнить операцию слияния.

Если массивы не упорядочены, или очень хочется деревом, то
1) Строим суффиксное дерево для массива a[].
2) Проходим по всем элементам массива b[] и смотрим, сколько раз подстрока из этого 1 элемента встречается в строке a[]. Это стандартная операция для суф. дерева: надо просто взять количество листьев в поддереве вершины, которая читается искомой строкой (в нашем случае - это непосредственный ребенок корня, к которому ведет строка, начинающаяся с символа b[i]).

Еще конкретнее - постройте дерево, найдите для каждой вершины количество листьев в поддереве (просто суммируя эти же значения для всех детей или рекурсивно или поднимаясь снизу-вверх). Потом просуммируйте эти значения для всех вершин, в которые из корня есть ребро начинающееся с символа b[i] для всех i.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
BacCM
@BacCM
C++ почти с рождения
Нда если массивы возрастающие зачем дерево?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы