How to implement a search for common elements of two arrays using a suffix tree?

Question

Programming

At the input we have two increasing arrays of integers: a[m], b[n].
You need to find the number of identical elements: a[i] == b[j].
The search must be implemented using a suffix tree, the number of actions must be of the order of m + n.
Tell me how you can organize such a search using a suffix tree?

Answer 1

For sorted arrays, simply perform a merge operation.
If the arrays are not ordered, or if you really want a tree, then
1) Build a suffix tree for the a[] array.
2) We go through all the elements of the array b[] and see how many times a substring from this 1 element occurs in the string a[]. This is a standard operation for suf. tree: you just need to take the number of leaves in the subtree of the vertex that is read by the search string (in our case, this is the immediate child of the root to which the string starting with b[i] leads).
Even more specifically, build a tree, find for each vertex the number of leaves in the subtree (simply summing the same values ​​for all children, or recursively, or going up from bottom to top). Then sum these values ​​for all vertices that have an edge from the root starting with symbol b[i] for all i.

Answer 2

NDA if the arrays are increasing, why the tree?