Finding subtuple in larger collection? I've got a flat array of &lt; 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:


This seems like a CS 101 problem, so I'm pretty sure I'm overdoing it.  
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&lt;Integer&gt; possibleStartIndices = new ArrayList&lt;Integer&gt;();
    int keyListSize = toFind.length;
    for (int i = 0; i &lt;= 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 &lt; indices.length; i++)
        indices[i] = startIndex + i;

    return indices;
}
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 &lt; haystack.length - needle.length; a++) {
        for (int b = 0; b &lt; needle.length; b++) {
            if (!haystack[a+b].equals(needle[b])) continue foo;
        }
        return a;
    }
    return -1;
}