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

 На входе у нас есть два возрастающих массива целых чисел: a[m], b[n].  

Нужно найти количество одинаковых элементов: a[i] == b[j].  

Поиск нужно реализовать с помощью суффиксного дерева, число действий должно быть порядка m + n.  
  

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

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

Если массивы не упорядочены, или очень хочется деревом, то   

1) Строим суффиксное дерево для массива a[].  

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

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

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