Finding subtuple in larger collection?

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]))
{
}
}

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

• This seems like a good place to use Boyer-Moore string searching.
– user806
Jan 27, 2011 at 16:43
• What about the "overlapping" case, i.e: should searching for "AA" in "AAA" return 0 and 1 as "start" indices? As it presently is in your code, it should, but if it is not a requirement (i.e. the searched-in string can be only a "stack" of searched-for string copies with some other strings outside and between them), it can possibly have some effect on the effectiveness of the algorithm and the size of the code implementing it. Jan 27, 2011 at 23:57
• very tempting. My fear is I will confuse the maintenance programmers though when they come back to the code and find my link to a string search algorithm in code that isn't parsing Strings (the objects are different types). If this was mission critical performance-wise, I'd make it work though. Also big +1 for dredging the answer to #1 one out of my neural off-line storage (probably tape). Jan 28, 2011 at 18:43
• @mlvljr Overlaps not a concern in this dataset; it breaks and drops to return as soon as the search key matches Jan 28, 2011 at 18:48

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

• +1 for dispensing with copyOfRange/Arrays.equals, stopping search needle.length early, and handling repeated values in search string correctly. However, I do think a BM impl may be helpful. Jan 28, 2011 at 1:34
• Thanks for your comment. I agree BM could be of benefit. I found it nonintuitive in the context of Object elements instead of chars, but it looks like a win.
– Ron
Jan 28, 2011 at 2:01
• Should not that be b < (needle.length + a)? Jan 28, 2011 at 20:24
• @mlvljr you are right - its broke. I think the fix should be: int b = a should change to int b = 0 and haystack[b] should be changed to haystack[a+b]. b is the index into needle, so b needs to range from 0 to needle.length. a is the index to haystack and the inner loop needs to add the offset b, so index into haystack should be a+b. I submitted an edit to fix it. Jan 28, 2011 at 21:18
• I implemented a BM version, but its far more complex for very little performance difference (worse in some test cases). Feb 1, 2011 at 1:41

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 new int[0];
}

• Good catch. When I started writing it I planned to map/reduce it several times to make it clear what was happening. I changed course in the middle but didn't refactor. Jan 28, 2011 at 18:47

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

• Fails if repeated values in search string: indexOf("aaab", "aab") should return 1. Jan 28, 2011 at 1:20
• Good catch. Updated accordingly. Jan 28, 2011 at 15:15
• I guess it will still come out with me missing some invariant or other and making an ass of myself again... I'll shut up then. Jan 28, 2011 at 15:20

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.