Hier ist eine O (mn) -Lösung. In Anbetracht der Tatsache, dass der Heuhaufen etwa 1000 lang ist und die Nadel 5 oder kleiner ist, ist der einfachste Code für die Suche wahrscheinlich der beste. Wenn Gleichheitstests jedoch teuer sind, können wir dies abschwächen, auch wenn ich mir nicht sicher bin, ob der Wechsel zu KMP oder BM angesichts der Tatsache, dass wir uns hier mit Object beschäftigen, so sehr helfen wird.
// 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;
}