Tengo una lista lineal de ceros y unos y necesito hacer coincidir varios patrones simples y encontrar la primera aparición. Por ejemplo, podría tener que encontrar0001101101, 01010100100, O10100100010 Dentro de una lista de longitud 8 millones. Solo necesito encontrar la primera aparición de cualquiera de ellas y luego devolver el índice en el que ocurre. Sin embargo, hacer el bucle y los accesos en la lista grande puede ser costoso, y prefiero no hacerlo muchas veces.

¿Hay un método más rápido que haciendo

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

Editar: Por cierto, he implementado este programa de acuerdo con el pseudocódigo anterior, y el rendimiento es bueno, pero nada espectacular. Estoy estimando que proceso unos 6 millones de bits por segundo en un solo núcleo de mi procesador. Estoy usando esto para el procesamiento de imágenes, y tendrá que pasar por unos pocos miles de imágenes de 8 megapíxeles, por lo que cada poco ayuda.

Editar: Si no está claro, estoy trabajando con una matriz de bits, por lo que solo hay dos posibilidades: UNA y CERO. Y está en C ++.

Editar: Gracias por los punteros a los algoritmos BM y KMP. Noté que, en la página de Wikipedia para BM, dice

El algoritmo preprocesa la cadena de destino (clave) que se está buscando, pero no la cadena que se está buscando (a diferencia de algunos algoritmos que preprocesan la cadena a buscar y luego puede amortizar el costo del preprocesamiento buscando repetidamente).

Eso parece interesante, pero no dio ningún ejemplo de tales algoritmos. ¿Algo así también ayudaría?