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