I can't think of how to optimise your searches; you have got two parallel linear searches, no three parallel linear searches, if I have understood the question correctly:
Through the individual Strings of array 1.
Through the individual Strings of array 2.
Through the length of the current String to see whether part of it matches.
So you are stuck with cubic complexity.
It is worthwhile seeing whether it is possible to make one of the arrays into a regular expression, then iterating through the other array looking for matches, but I don't know whether that is any faster.
There is one way, as I think... but could involve a bit of preparation work on those arrays before the search operation.
step1: sort both the arrays [ascending or descending, but make sure both of the arrays are in the same order].
step2: start searching in order, and break the moment if an element in array2 is not found in array1.
As I mentioned, there is an added overhead of sorting the arrays before the operation, but if you can handle that, then this could optimize your search.