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

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);

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.

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.

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.

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