What is the fastest way to find an array within another array in Java?

Question

Is there any equivalent of String.indexOf() for arrays? If not, is there any faster way to find an array within another other than a linear search?

Answer 1

As far as I know, there is NO way to find an array within another without a linear search. String.indexOf uses a linear search, just inside a library.

You should write a little library called indexOf that takes two arrays, then you will have code that looks just like indexOf.

But no matter how you do it, it's a linear search under the covers.

edit:

After looking at @ahmadabolkader's answer I kind of take this back. Although it's still a linear search, it's not as simple as just "implement it" unless you are restricted to fairly small test sets/results.

The problem comes when you want to see if ...aaaaaaaaaaaaaaaaaab fits into a string of (x1000000)...aaaaaaaaab (in other words, strings that tend to match most places in the search string).

My thought was that as soon as you found a first character match you'd just check all subsequent characters one-on-one, but that performance would degrade terrifyingly when most of the characters matched most of the time. There was a rolling hash method in @a12r's answer that sounded much better if this is a real-world problem and not just an assignment.

I'm just going to vote for @a12r's answer because of those awesome Wikipedia references.

Answer 2

Normally the way you find things in collections in java is

• put them in a hashmap (dictionary) and look them up by their hash.
• loop through each object and test its equality

(1) won't work for you because an array object's hash won't tell you that the contents are the same. You could write some sort of wrapper that would create a hashcode based on the contents (you'd also have to make sure equals returned values consistent with that).

(2) also will require a bit of work because object equality for arrays will only test that the objects are the same. You'd need to wrap the arrays with a test of the contents.

So basically, not unless you write it yourself.

Answer 3

The short answer is no - there is no faster way to find an array within an array by using some existing construct in Java. Based on what you described, consider creating a HashSet of arrays instead of an array of arrays.

Answer 4

You mean you have an array which elements also are array elements? If that is the case and the elements are sorted you might be able to use binarysearch from java.util.Arrays

Answer 5

Regardless of the elements of your arrays, I believe this is not much different than the string search problem.

This article provides a general intro to the various known algorithms.

Rabin-Karp and KMP might be your best options.

You should be able to find Java implementations of these algorithms and adapt them to your problem.

Answer 6

List<Object> list = Arrays.asList(myArray);
Collections.sort(list);
int index = Collections.binarySearch(list, find);

OR

public static int indexOf(Object[][] array, Object[] find){
  for (int i = 0; i < array.length(); i ++){
    if (Arrays.equals(array[i], find)){
      return i;
    }
  }
  return -1;
}

OR

public static int indexOf(Object[] array, Object find){
  for (int i = 0; i < array.length(); i ++){
    if (array[i].equals(find)){
      return i;
    }
  }
  return -1;
}

OR

Object[] array = ...
int index = Arrays.asList(array).indexOf(find);