Ich habe eine lineare Liste von Nullen und Einsen, und ich muss mehrere einfache Muster abgleichen und das erste Vorkommen finden. Zum Beispiel könnte ich finden müssen0001101101, 01010100100, ODER10100100010 innerhalb einer Liste von Länge 8 Millionen. Ich muss nur das erste Vorkommen von beidem finden und dann den Index zurückgeben, an dem es auftritt. Das Durchlaufen und Zugreifen über die große Liste kann jedoch teuer sein, und ich möchte es lieber nicht zu oft tun.

Gibt es eine schnellere Methode als dies zu tun?

foreach (patterns) {
    for (i=0; i < listLength; i++)
        for(t=0; t < patternlength; t++)
            if( list[i+t] != pattern[t] ) {
                 break;
            }
            if( t == patternlength - 1 ) {
                 return i;  // pattern found!
            }
        }
    }
}

Bearbeiten: Übrigens habe ich dieses Programm gemäß dem obigen Pseudocode implementiert, und die Leistung ist in Ordnung, aber nichts Spektakuläres. Ich schätze, dass ich ungefähr 6 Millionen Bits pro Sekunde auf einem einzelnen Kern meines Prozessors verarbeite. Ich verwende dies für die Bildverarbeitung, und es müssen einige tausend 8-Megapixel-Bilder durchgearbeitet werden, damit jedes kleine bisschen hilft.

Bearbeiten: Wenn es nicht klar ist, arbeite ich mit einem Bit-Array, daher gibt es nur zwei Möglichkeiten: EINS und NULL. Und es ist in C ++.

Bearbeiten: Vielen Dank für die Hinweise zu BM- und KMP-Algorithmen. Ich habe festgestellt, dass auf der Wikipedia-Seite für BM steht

Der Algorithmus verarbeitet die gesuchte Zielzeichenfolge (den gesuchten Schlüssel) vor, nicht jedoch die gesuchte Zeichenfolge (im Gegensatz zu einigen Algorithmen, die die zu durchsuchende Zeichenfolge vorverarbeiten und dann die Kosten der Vorverarbeitung durch wiederholtes Suchen amortisieren können).

Das sieht interessant aus, aber es gab keine Beispiele für solche Algorithmen. Würde so etwas auch helfen?