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

Question

[Николай Шепелев]

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

Подскажите, как можно организовать такой поиск именно с помощью суффиксного дерева?

Comments

[Денис Загаевский]

Что такое суффиксное дерево? Какими свойствами оно обладает?

[Николай Шепелев]

Денис Загаевский: https://en.wikipedia.org/wiki/Suffix_tree, https://visualgo.net/suffixtree

[Денис Загаевский]

Николай Шепелев: не, ну спасибо, конечно))) но может ты это почитаешь? И попробуешь из свойств понять, как применить?

[Николай Шепелев]

Денис Загаевский: Почитал, не понял, поэтому и прошу помощи.

[Денис Загаевский]

Николай Шепелев: так какие свойства есть?

[Николай Шепелев]

Денис Загаевский: Что вы подразумеваете под свойствами?

[Денис Загаевский]

Николай Шепелев: ясно, делать ты ничего не хочешь, хочешь лабу на халяву.

[Николай Шепелев]

Денис Загаевский: А вы участвовали в каком-нибудь шоу экстрасенсов? :)

[Денис Загаевский]

Николай Шепелев: ну видно же по тебе. Если бы ты начал думать, может помог бы тебе.

[Николай Шепелев]

Денис Загаевский: Да, нет, мне просто нужно объяснить каким боком можно в данной задаче использовать суффиксное дерево, именно за O(m + n).

Answer 1

[Wataru]

Для отсортированных массивов достаточно просто выполнить операцию слияния.

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

Еще конкретнее - постройте дерево, найдите для каждой вершины количество листьев в поддереве (просто суммируя эти же значения для всех детей или рекурсивно или поднимаясь снизу-вверх). Потом просуммируйте эти значения для всех вершин, в которые из корня есть ребро начинающееся с символа b[i] для всех i.

Answer 2

[Василий Мельников]

Нда если массивы возрастающие зачем дерево?