Eu tenho uma lista linear de zeros e uns e preciso combinar vários padrões simples e encontrar a primeira ocorrência. Por exemplo, talvez eu precise encontrar0001101101, 01010100100OU10100100010 dentro de uma lista de comprimento de 8 milhões. Eu só preciso encontrar a primeira ocorrência de qualquer um e, em seguida, retornar o índice em que ocorre. No entanto, fazer o loop e acessar a lista grande pode ser caro, e prefiro não fazê-lo muitas vezes.

Existe um método mais rápido do que fazer

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: BTW, eu tenho implementado este programa de acordo com o pseudocódigo acima, e o desempenho é OK, mas nada de espetacular. Eu estou estimando que eu processo cerca de 6 milhões de bits por segundo em um único núcleo do meu processador. Eu estou usando isso para processamento de imagem, e ele vai ter que passar por alguns milhares de imagens de 8 megapixels, então cada pouquinho ajuda.

Editar: Se não está claro, estou trabalhando com um array pequeno, então há apenas duas possibilidades: ONE e ZERO. E é em C ++.

Editar: Obrigado pelos ponteiros para os algoritmos BM e KMP. Eu notei que, na página da Wikipedia para BM, diz

O algoritmo pré-processa a sequência de caracteres (chave) que está sendo pesquisada, mas não a sequência pesquisada (diferentemente de alguns algoritmos que pré-processam a sequência a ser pesquisada e podem amortizar a despesa do pré-processamento pesquisando repetidamente).

Isso parece interessante, mas não deu exemplos de tais algoritmos. Algo assim também ajudaria?