Return to Revisions

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