Finding subtuple in larger collection?

Question

I've got a flat array of < 1000 items and I need to find the indices of a smaller tuple/array within the array. The tuple to find can be a varying length (generally between 2 and 5 items, order is important).

This is my initial naive implementation. My main concerns are:

1. This seems like a CS 101 problem, so I'm pretty sure I'm overdoing it.
2. Readability. I can break this down into smaller methods, but it's essentially a utility function in a much larger class. I guess I could extract it into its own class, but that feels like overkill as well. As-is, it's just too long for me to grok the whole thing in one pass.

public int[] findIndices(final Object[] toSearch, final Object[] toFind) 
{
    Object first = toFind[0];

    List<Integer> possibleStartIndices = new ArrayList<Integer>();
    int keyListSize = toFind.length;
    for (int i = 0; i <= toSearch.length - keyListSize; i++) 
    {
        if (first.equals(toSearch[i])) 
        {
            possibleStartIndices.add(i);
        }
    }

    int[] indices = new int[0];
    for (int startIndex : possibleStartIndices) 
    {
        int endIndex = startIndex + keyListSize;
        Object[] possibleMatch = Arrays.copyOfRange(toSearch, startIndex, endIndex);
        if (Arrays.equals(toFind, possibleMatch)) {
            indices = toIndexArray(startIndex, endIndex);
            break;
        }
    }
    return indices;
}

private int[] toIndexArray(final int startIndex, final int endIndex) 
{
    int[] indices = new int[endIndex - startIndex];
    for (int i = 0; i < indices.length; i++)
        indices[i] = startIndex + i;

    return indices;
}

Answer 1

Here is an O(mn) solution. Given that haystack is about 1000 in length and needle is 5 or smaller, the simplest code to do the search is probably the best. But if testing for equality is expensive, there are things we can do to mitigate that, although I'm not sure switching to KMP or BM will help so much given that we're dealing with Object here.

// assumes no null entries
// returns starting index of first occurrence of needle within haystack or -1
public int indexOf(final Object[] haystack, final Object[] needle) 
{
    foo: for (int a = 0; a < haystack.length - needle.length; a++) {
        for (int b = 0; b < needle.length; b++) {
            if (!haystack[a+b].equals(needle[b])) continue foo;
        }
        return a;
    }
    return -1;
}

Answer 2

As a quick tip, I would suggest you skip the step of finding possible start indexes.

Instead, as you are already iterating over the whole list to find possible start indexes, then why don't you check that index right away when you find it? Would be something like:

public int[] findIndices(final Object[] toSearch, final Object[] toFind) 
{
    Object first = toFind[0];

    int keyListSize = toFind.length;
    for (int startIndex = 0; startIndex <= toSearch.length - keyListSize; startIndex++) 
    {
        if (first.equals(toSearch[startIndex])) 
        {
            int endIndex = startIndex + keyListSize;
            Object[] possibleMatch = Arrays.copyOfRange(toSearch, startIndex, endIndex);
            if (Arrays.equals(toFind, possibleMatch)) {
                return toIndexArray(startIndex, endIndex);
            }
        }
    }

    return new int[0];
}

Answer 3

Edit Original code is wrong. Added better below.

Something like this could do it in one pass (I think - I haven't checked it to death). Note that I only return the first index as the next ones can be calculated easily by just doing a new array i, i+1, ..., i+n-1 etc. Simpler (and slower) than Boyer Moore but still O(n):

public static <T> int indexOf(final T[] target, final T[] candidate) {

    for (int t = 0, i = 0; i < target.length; i++) {
        if (target[i].equals(candidate[t])) {
            t++;
            if (t == candidate.length) {
                return i-t+1;
            }
        } else {
            t = 0;
        }
    }

    return -1;
}

Edit: This should work better, no? It's not as clean and simple, but now I'm more confident that it's actually correct. What happens is that when we fail, we backtrack and restart.

public static <T> int indexOf(final T[] target, final T[] candidate) {
    int t = 0, i = 0;    
    while (i < target.length)
    {
        if (target[i].equals(candidate[t])) {
            t++;
            if (t == candidate.length) {
                return i-t+1;
            }
        } else {
            i -= t;
            t = 0;
        }
        i++;
    }    
    return -1;
}

Answer 4

For <1000 items, unless checking each item is prohibitively expensive, I'd say Pablo has the right idea of just checking on the first pass. This eliminates O(n) from the algorithm. For a larger list, or where checking each item is expensive, something more complicated like a Boyer-Moore style algorithm like mtnygard suggests might be appropriate.