Standard API way to check if one array is contained in another.

Question

I have two byte[] arrays in a method like this:

private static boolean containsBytes(byte[] body, byte[] checker){
  //Code you do not want to ever see here.
}

I want to, using the standard API as much as possible, determine if the series contained in the checker array exists anywhere in the body array.

Right now I'm looking at some nasty code that did a hand-crafted algorithm. The performance of the algorithm is OK, which is about all you can say for it. I'm wondering if there is a more standard api way to accomplish it. Otherwise, I know how to write a readable hand-crafted one.

To get a sense of scale here, the checker array would not be larger than 48 (probably less) and the body might be a few kb large at most.

Answer 1

I don't know of anything in the standard API to help you here. There may be something in a third party library, although it would potentially need to be implemented repeatedly, once for each primitive type :(

EDIT: I was going to look for Boyer-Moore, but this answer was added on my phone, and I ran out of time :)

Depending on the data and your requirements, you may find that a brute force approach is absolutely fine - and a lot simpler to implement than any of the fancier algorithms available. The simple brute force approach is generally my first port of call - it often turns out to be perfectly adequate :)

Answer 2

You probably already know this, but what you're trying to (re-)implement is basically a string search:

http://en.wikipedia.org/wiki/String_searching_algorithm

The old code might in fact be an implementation of one of the string search algorithms; for better performance, it might be good to implement one of the other algorithms. You didn't mention how often this method is going to be called, which would help to decide whether it's worth doing that.

Answer 3

Not in the standard library (like Jon Skeet said, probably nothing there that does this) but Guava could help you here with its method Bytes.indexOf(byte[] array, byte[] target).

boolean contained = Bytes.indexOf(body, checker) != -1;

Plus, the same method exists in the classes for the other primitive types as well.

Answer 4

The collections framework can both cheaply wrap an array in the List interface and search for a sublist. I think this would work reasonably well:

import java.util.Arrays;
import java.util.Collections;
boolean found = Collections.indexOfSubList(Arrays.asList(body), Arrays.asList(checker) >= 0;