Mam liniową listę zer i jedynek i muszę dopasować wiele prostych wzorów i znaleźć pierwsze wystąpienie. Na przykład muszę znaleźć0001101101, 01010100100, LUB10100100010 na liście o długości 8 milionów. Muszę tylko znaleźć pierwsze wystąpienie któregokolwiek z nich, a następnie zwrócić indeks, w którym występuje. Jednak wykonywanie pętli i dostępów na dużej liście może być kosztowne, a wolałbym nie robić tego zbyt wiele razy.

Czy jest szybsza metoda niż robienie

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

Edytować: BTW, zaimplementowałem ten program zgodnie z powyższym pseudokodem, a wydajność jest OK, ale nic spektakularnego. Szacuję, że przetwarzam około 6 milionów bitów na sekundę na jednym rdzeniu mojego procesora. Używam tego do przetwarzania obrazu i będzie musiał przejść przez kilka tysięcy zdjęć o rozdzielczości 8 megapikseli, więc każdy drobiazg pomaga.

Edytować: Jeśli nie jest jasne, pracuję z tablicą bitową, więc są tylko dwie możliwości: JEDNA i ZEROWA. I jest w C ++.

Edytować: Dziękujemy za wskaźniki do algorytmów BM i KMP. Zauważyłem, że na stronie Wikipedii dla BM, mówi

Algorytm przetwarza poszukiwany ciąg (klucz) docelowy, ale nie przeszukiwany ciąg (w przeciwieństwie do niektórych algorytmów, które przetwarzają wstępnie przeszukiwany ciąg, a następnie mogą amortyzować koszt przetwarzania wstępnego poprzez wielokrotne przeszukiwanie).

To wygląda interesująco, ale nie podaje żadnych przykładów takich algorytmów. Czy coś takiego też pomoże?