Qual é o algoritmo de pesquisa de substring mais rápido?

OK, então eu não pareço um idiota, vou declarar o problema / requisitos mais explicitamente:

• Agulha (padrão) e palheiro (texto a ser pesquisado) são seqüências terminadas em nulo no estilo C. Nenhuma informação de comprimento é fornecida; se necessário, deve ser calculado.
• A função deve retornar um ponteiro para a primeira correspondência, ou NULLse nenhuma correspondência for encontrada.
• Casos de falha não são permitidos. Isso significa que qualquer algoritmo com requisitos de armazenamento não constante (ou grande constante) precisará ter um caso de fallback para falha de alocação (e o desempenho no cuidado de fallback contribui para o pior desempenho).
• A implementação deve ser em C, embora uma boa descrição do algoritmo (ou link para tal) sem código também seja adequada.

... bem como o que quero dizer com "mais rápido":

• Determinístico O(n)onde n= comprimento do palheiro. (Mas pode ser possível usar idéias de algoritmos que são normalmente O(nm)(por exemplo, hash rotativo) se elas forem combinadas com um algoritmo mais robusto para fornecer O(n)resultados determinísticos ).
• Nunca apresenta desempenho (mensurável; alguns relógios if (!needle[1])são aceitáveis) pior que o algoritmo ingênuo de força bruta, especialmente em agulhas muito curtas, que provavelmente são o caso mais comum. (A sobrecarga pesada de pré-processamento incondicional é ruim, pois está tentando melhorar o coeficiente linear para agulhas patológicas às custas de prováveis ​​agulhas.)
• Dada uma agulha e um palheiro arbitrários, desempenho comparável ou melhor (não inferior a 50% do tempo de pesquisa) em comparação com qualquer outro algoritmo amplamente implementado.
• Além dessas condições, estou deixando a definição de "mais rápido" em aberto. Uma boa resposta deve explicar por que você considera a abordagem sugerida como "mais rápida".

Minha implementação atual é aproximadamente 10% mais lenta e 8 vezes mais rápida (dependendo da entrada) do que a implementação de duas vias da glibc.

Atualização: Meu algoritmo ideal atual é o seguinte:

• Para agulhas de comprimento 1, use strchr.
• Para agulhas de comprimento 2 a 4, use palavras de máquina para comparar 2 a 4 bytes de uma vez da seguinte maneira: Pré-carregue a agulha em um número inteiro de 16 ou 32 bits com deslocamento de bits e faça o ciclo de saída de bytes antigos / novos bytes do palheiro a cada iteração . Cada byte do palheiro é lido exatamente uma vez e incorre em uma verificação contra 0 (final da string) e uma comparação de 16 ou 32 bits.
• Para agulhas de comprimento> 4, use o algoritmo Bidirecional com uma tabela de deslocamento ruim (como Boyer-Moore), que é aplicada apenas ao último byte da janela. Para evitar a sobrecarga de inicializar uma tabela de 1kb, o que seria uma perda líquida para muitas agulhas de comprimento moderado, mantenho uma matriz de bits (32 bytes) marcando quais entradas na tabela de deslocamento são inicializadas. Os bits não configurados correspondem aos valores de bytes que nunca aparecem na agulha, para os quais é possível uma mudança no comprimento total da agulha.

As grandes questões que me restam são:

• Existe uma maneira de fazer melhor uso da tabela de turnos ruim? A Boyer-Moore faz o melhor uso possível, digitalizando para trás (da direita para a esquerda), mas o Two-Way exige uma digitalização da esquerda para a direita.
• Os únicos dois algoritmos candidatos viáveis ​​que encontrei para o caso geral (sem condições de desempenho quadrático ou de falta de memória) são a Correspondência de duas vias e a seqüência de caracteres em alfabetos ordenados . Mas existem casos facilmente detectáveis ​​em que algoritmos diferentes seriam ótimos? Certamente muitos dos algoritmos O(m)(onde mestá o comprimento da agulha) no espaço podem ser usados ​​para m<100isso. Também seria possível usar algoritmos quadráticos, na pior das hipóteses, se houver um teste fácil para agulhas que provavelmente requer apenas tempo linear.

Pontos de bônus por:

• Você pode melhorar o desempenho assumindo que a agulha e o palheiro são UTF-8 bem formados? (Com caracteres de tamanhos variáveis ​​de bytes, a boa formação impõe alguns requisitos de alinhamento de cordas entre a agulha e o palheiro e permite trocas automáticas de 2-4 bytes quando um byte incompatível é encontrado. Mas essas restrições compram muito / qualquer coisa além do que cálculos máximos de sufixos, boas mudanças de sufixos, etc. já oferecem vários algoritmos?)

Nota: Conheço bem a maioria dos algoritmos existentes, mas não o desempenho deles na prática. Aqui está uma boa referência para que as pessoas não continuem me fornecendo referências sobre algoritmos como comentários / respostas: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Crie uma biblioteca de testes com prováveis ​​agulhas e palheiros. Perfile os testes em vários algoritmos de pesquisa, incluindo força bruta. Escolha o que apresenta melhor desempenho com seus dados.

Boyer-Moore usa uma tabela de caracteres incorreta com uma tabela de sufixos boa.

Boyer-Moore-Horspool usa uma tabela de caracteres incorreta.

Knuth-Morris-Pratt usa uma tabela de correspondência parcial.

Rabin-Karp usa hashes em execução.

Todos eles trocam custos indiretos por comparações reduzidas em um grau diferente; portanto, o desempenho no mundo real dependerá dos comprimentos médios da agulha e do palheiro. Quanto mais sobrecarga inicial, melhor com entradas mais longas. Com agulhas muito curtas, a força bruta pode vencer.

Editar:

Um algoritmo diferente pode ser melhor para encontrar pares de bases, frases em inglês ou palavras únicas. Se houvesse um melhor algoritmo para todas as entradas, ele teria sido divulgado.

Pense na pequena mesa a seguir. Cada ponto de interrogação pode ter um melhor algoritmo de pesquisa diferente.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

Este deve realmente ser um gráfico, com um intervalo de entradas mais curtas a mais longas em cada eixo. Se você plotasse cada algoritmo nesse gráfico, cada um teria uma assinatura diferente. Alguns algoritmos sofrem muita repetição no padrão, o que pode afetar usos como a pesquisa de genes. Alguns outros fatores que afetam o desempenho geral estão pesquisando o mesmo padrão mais de uma vez e pesquisando padrões diferentes ao mesmo tempo.

Se eu precisasse de um conjunto de amostras, acho que rasparia um site como o google ou a wikipedia e retiraria o html de todas as páginas de resultados. Para um site de pesquisa, digite uma palavra e use uma das frases de pesquisa sugeridas. Escolha alguns idiomas diferentes, se aplicável. Usando páginas da web, todos os textos seriam curtos a médios; portanto, mescle páginas suficientes para obter textos mais longos. Você também pode encontrar livros de domínio público, registros legais e outros grandes corpos de texto. Ou apenas gere conteúdo aleatório escolhendo palavras de um dicionário. Mas o objetivo do perfil é testar o tipo de conteúdo que você estará pesquisando; portanto, use amostras do mundo real, se possível.

Deixei curto e longo vago. Para a agulha, penso em curto com menos de 8 caracteres, médio com menos de 64 caracteres e com menos de 1k. Para o palheiro, penso em curto como abaixo de 2 ^ 10, médio como abaixo de 2 ^ 20 e com até 2 ^ 30 caracteres.

Publicado em 2011, acredito que pode muito bem ser o algoritmo "Correspondência simples de cadeia de espaço constante em tempo real" de Dany Breslauer, Roberto Grossi e Filippo Mignosi.

Atualizar:

Em 2014, os autores publicaram essa melhoria: Rumo à correspondência ideal de cadeias compactadas .

O link http://www-igm.univ-mlv.fr/~lecroq/string/index.html para o qual você aponta é uma excelente fonte e resumo de alguns dos algoritmos de correspondência de string mais conhecidos e pesquisados.

As soluções para a maioria dos problemas de pesquisa envolvem trade-offs com relação aos requisitos de pré-processamento, tempo e espaço. Nenhum algoritmo será ideal ou prático em todos os casos.

Se seu objetivo é projetar um algoritmo específico para pesquisa de strings, ignore o restante do que tenho a dizer: se você deseja desenvolver uma rotina de serviço de pesquisa de strings generalizada, tente o seguinte:

Passe algum tempo revisando os pontos fortes e fracos dos algoritmos que você já referenciou. Conduza a revisão com o objetivo de encontrar um conjunto de algoritmos que cubram o alcance e o escopo das pesquisas de cadeia de caracteres nas quais você está interessado. Em seguida, crie um seletor de pesquisa de front-end com base em uma função classificadora para direcionar o melhor algoritmo para as entradas fornecidas. Dessa forma, você pode empregar o algoritmo mais eficiente para fazer o trabalho. Isso é particularmente eficaz quando um algoritmo é muito bom para determinadas pesquisas, mas se degrada pouco. Por exemplo, a força bruta é provavelmente a melhor para agulhas de comprimento 1, mas se degrada rapidamente à medida que o comprimento da agulha aumenta, e o algoritmo sustik-moorepode se tornar mais eficiente (em alfabetos pequenos), então para agulhas mais longas e alfabetos maiores, os algoritmos KMP ou Boyer-Moore podem ser melhores. Estes são apenas exemplos para ilustrar uma possível estratégia.

A abordagem de algoritmos múltiplos não é uma idéia nova. Acredito que ele tenha sido empregado por alguns pacotes comerciais de classificação / pesquisa (por exemplo, o SYNCSORT geralmente usado em mainframes implementa vários algoritmos de classificação e usa heurística para escolher o "melhor" para as entradas fornecidas)

Cada algoritmo de busca apresenta diversas variações que podem fazer diferenças significativas em seu desempenho, como, por exemplo, ilustra este artigo .

Faça uma avaliação comparativa do seu serviço para categorizar as áreas em que são necessárias estratégias de pesquisa adicionais ou para ajustar com mais eficiência a função do seletor. Essa abordagem não é rápida ou fácil, mas se bem feita, pode produzir resultados muito bons.

Fiquei surpreso ao ver nosso relatório técnico citado nesta discussão; Eu sou um dos autores do algoritmo que foi nomeado Sustik-Moore acima. (Não usamos esse termo em nosso artigo.)

Queria enfatizar aqui que, para mim, a característica mais interessante do algoritmo é que é bastante simples provar que cada letra é examinada ao mesmo tempo. Para versões anteriores de Boyer-Moore, eles provaram que cada letra é examinada no máximo 3 e depois 2 vezes no máximo, e essas provas estavam mais envolvidas (ver citações em papel). Portanto, também vejo um valor didático na apresentação / estudo dessa variante.

No artigo, também descrevemos outras variações voltadas para a eficiência, enquanto relaxamos as garantias teóricas. É um artigo breve e, na minha opinião, o material deve ser compreensível para um graduado médio do ensino médio.

Nosso principal objetivo era chamar a atenção desta versão para outras pessoas que possam aprimorá-la ainda mais. A pesquisa de strings tem muitas variações e, por si só, não conseguimos pensar em tudo em que essa idéia poderia trazer benefícios. (Texto fixo e padrão de alteração, texto diferente de padrão fixo, pré-processamento possível / não possível, execução paralela, localizando subconjuntos correspondentes em textos grandes, permitir erros, correspondências próximas etc., etc.)

O algoritmo de pesquisa de substring mais rápido dependerá do contexto:

1. o tamanho do alfabeto (por exemplo, DNA vs inglês)
2. o comprimento da agulha

O artigo de 2010 "O problema exato de correspondência de cordas: uma avaliação experimental abrangente" fornece tabelas com tempos de execução para 51 algoritmos (com diferentes tamanhos de alfabeto e comprimentos de agulhas), para que você possa escolher o melhor algoritmo para o seu contexto.

Todos esses algoritmos têm implementações em C, além de um conjunto de testes aqui:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Uma pergunta muito boa. Basta adicionar alguns pedacinhos ...

1. Alguém estava falando sobre a correspondência da sequência de DNA. Mas para a sequência de DNA, o que geralmente fazemos é construir uma estrutura de dados (por exemplo, matriz de sufixos, árvore de sufixos ou índice FM) para o palheiro e combinar muitas agulhas contra ele. Esta é uma pergunta diferente.

2. Seria realmente ótimo se alguém gostaria de comparar vários algoritmos. Existem benchmarks muito bons na compactação e na construção de matrizes de sufixos, mas eu não vi um benchmark na correspondência de strings. Os possíveis candidatos a palheiros podem ser do benchmark da SACA .

3. Alguns dias atrás, eu estava testando a implementação de Boyer-Moore na página que você recomendou (EDIT: preciso de uma chamada de função como memmem (), mas não é uma função padrão, por isso decidi implementá-la). Meu programa de benchmarking usa palheiro aleatório. Parece que a implementação de Boyer-Moore nessa página é vezes mais rápida que o memmem da glibc () e a strnstr do Mac (). Caso você esteja interessado, a implementação está aqui e o código de benchmarking está aqui . Definitivamente, essa não é uma referência realista, mas é um começo.

Eu sei que é uma pergunta antiga, mas a maioria das tabelas de turnos ruins é de um único personagem. Se fizer sentido para o seu conjunto de dados (por exemplo, especialmente se houver palavras escritas), e se você tiver espaço disponível, poderá obter uma aceleração dramática usando uma tabela de deslocamento ruim feita de n-gramas em vez de caracteres únicos.

Use stdlib strstr:

char *foundit = strstr(haystack, needle);

Foi muito rápido, levei apenas 5 segundos para digitar.

Aqui está a implementação de pesquisa do Python , usada em todo o núcleo. Os comentários indicam que ele usa uma tabela compactada boyer-moore delta 1 .

Fiz algumas experiências bastante extensas com a busca por cadeias de caracteres, mas foi para várias cadeias de busca. As implementações de montagem do Horspool e Bitap geralmente podem se defender de algoritmos como o Aho-Corasick, para contagens de padrões baixos.

Um strchralgoritmo "Procurar por um único caractere correspondente" (ala ) mais rápido .

Anotações importantes:

• Essas funções usam um gcccompilador "número / contagem de zeros (à esquerda | à direita)" intrínseco __builtin_ctz. É provável que essas funções sejam rápidas apenas em máquinas com instruções que executam essa operação (por exemplo, x86, ppc, arm).

• Essas funções assumem que a arquitetura de destino pode executar cargas desalinhadas de 32 e 64 bits. Se sua arquitetura de destino não suportar isso, você precisará adicionar alguma lógica de inicialização para alinhar corretamente as leituras.

• Essas funções são neutras no processador. Se a CPU de destino tiver instruções vetoriais, você poderá fazer (muito) melhor. Por exemplo, a strlenfunção abaixo usa SSE3 e pode ser modificada trivialmente para XOR os bytes verificados para procurar um byte diferente de 0. Benchmarks realizados em um laptop Core 2 de 2,66 GHz executando o Mac OS X 10.6 (x86_64):

  • 843,433 MB / s para strchr
  • 2656.742 MB / s para findFirstByte64
  • 13094.479 MB / s para strlen

... uma versão de 32 bits:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... e uma versão de 64 bits:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

Editar 2011/06/04 O OP indica nos comentários que esta solução possui um "bug intransponível":

pode ler além do byte procurado ou do terminador nulo, o que poderia acessar uma página ou página não mapeada sem permissão de leitura. Você simplesmente não pode usar leituras grandes em funções de string, a menos que estejam alinhadas.

Isso é tecnicamente verdadeiro, mas se aplica a praticamente qualquer algoritmo que opera em blocos maiores que um único byte, incluindo o método sugerido pelo OP nos comentários:

Uma strchrimplementação típica não é ingênua, mas é um pouco mais eficiente do que o que você deu. Veja o final disso para o algoritmo mais utilizado: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Também não tem nada a ver com o alinhamento propriamente dito. É verdade que isso pode causar o comportamento discutido na maioria das arquiteturas comuns em uso, mas isso tem mais a ver com detalhes de implementação de microarquitetura - se a leitura desalinhada ultrapassar um limite de 4K (novamente, típico), essa leitura causará um programa falha de terminação se o próximo limite de página de 4K não estiver mapeado.

Mas isso não é um "erro" no algoritmo dado na resposta - esse comportamento ocorre porque funções como strchre strlennão aceitam um lengthargumento para limitar o tamanho da pesquisa. A pesquisa char bytes[1] = {0x55};, que, para os propósitos de nossa discussão, acaba por ser colocada no final de um limite de página de VM de 4K e a próxima página não é mapeada, com strchr(bytes, 0xAA)(onde strchré uma implementação de byte por vez) falha exatamente mesma maneira. O mesmo vale para o strchrprimo relacionado strlen.

Sem lengthargumento, não há como saber quando você deve sair do algoritmo de alta velocidade e voltar para um algoritmo de byte a byte. Um "bug" muito mais provável seria ler "além do tamanho da alocação", o que tecnicamente resulta de undefined behavioracordo com os vários padrões da linguagem C e seria sinalizado como erro por algo parecido valgrind.

Em resumo, qualquer coisa que opere em pedaços maiores que bytes deve ser mais rápida, como esse código de respostas faz e o código indicado pelo OP, mas deve ter uma semântica de leitura precisa de bytes, provavelmente será "buggy" se não houver lengthargumento para controlar os casos de canto da "última leitura".

O código nesta resposta é um kernel para poder encontrar rapidamente o primeiro byte em um pedaço natural de tamanho de palavra da CPU, se a CPU de destino tiver uma ctzinstrução rápida . É trivial adicionar coisas como garantir que ele funcione apenas nos limites naturais alinhados corretamente ou em alguma forma de lengthlimite, o que permitiria que você saísse do kernel de alta velocidade e passasse a uma verificação mais lenta, byte a byte.

O OP também declara nos comentários:

Quanto à sua otimização ctz, isso só faz diferença para a operação de cauda O (1). Poderia melhorar o desempenho com pequenas seqüências de caracteres (por exemplo, strchr("abc", 'a');mas certamente não com sequências de qualquer tamanho maior).

Se essa afirmação é verdadeira ou não, depende muito da microarquitetura em questão. Usando o modelo de pipeline RISC canônico de 4 estágios, é quase certamente verdade. Mas é extremamente difícil dizer se isso é verdade para uma CPU super escalar contemporânea fora de ordem, em que a velocidade do núcleo pode minar totalmente a velocidade de streaming da memória. Nesse caso, não é apenas plausível, mas bastante comum, que exista uma grande lacuna no "número de instruções que podem ser retiradas" em relação ao "número de bytes que podem ser transmitidos" para que você tenha "o número de instruções que podem ser retiradas para cada byte que pode ser transmitido ". Se isso for grande o suficiente, a ctzinstrução + shift pode ser feita "de graça".

Basta procurar "strstr mais rápido" e, se vir algo de interesse, pergunte-me.

Na minha opinião, você impõe muitas restrições a si mesmo (sim, todos queremos linear sub-linear no max searcher); no entanto, é preciso um programador real para intervir; até então, acho que a abordagem de hash é simplesmente uma solução bacana para o limbo ( bem reforçado pelo BNDM para padrões mais curtos de 2 a 16).

Apenas um exemplo rápido:

Fazendo Pesquisar por padrão (32bytes) em String (206908949bytes) como-um-line ... Skip-Performance (maior-the-melhor): 3041%, 6801754 salta / iterações Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade desempenho: 3483KB / relógio

Fazendo Pesquisar por padrão (32bytes) em String (206908949bytes) como-um-line ... Skip-Performance (maior-the-melhor): 1,554%, 13307181 salta / iterações Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg desempenho: 2434KB / relógio

Fazendo Pesquisa de Padrão (32 bytes) na Cadeia de caracteres (206908949 bytes) como uma linha ... Desempenho em Saltos (maior o melhor): 129%, 160239051 ignora / iterações Hits de duas vias / relógios de duas vias: 0/816 Dois - Desempenho de maneira: 247KB / relógio

Sanmayce,
Atenciosamente

O algoritmo bidirecional que você mencionou na sua pergunta (que por sinal é incrível!) Foi recentemente aprimorado para trabalhar com eficiência em palavras multibyte ao mesmo tempo: Correspondência otimizada de cadeias compactadas .

Não li o artigo inteiro, mas parece que eles dependem de algumas instruções especiais novas da CPU (incluídas no SSE 4.2), sendo O (1) por sua complexidade de tempo, embora, se não estiverem disponíveis, possam simule-os no tempo O (log log w) para palavras em w bits que não soem muito ruins.

Você pode implementar, digamos, 4 algoritmos diferentes. A cada M minutos (a ser determinado empiricamente), execute todos os 4 nos dados reais atuais. Acumule estatísticas sobre N execuções (também TBD). Em seguida, use apenas o vencedor pelos próximos M minutos.

Registre estatísticas no Wins para poder substituir algoritmos que nunca vencem por novos. Concentre os esforços de otimização na rotina mais vencedora. Preste atenção especial às estatísticas após qualquer alteração no hardware, banco de dados ou fonte de dados. Inclua essas informações no registro de estatísticas, se possível, para que você não precise descobrir isso a partir da data / hora do registro.

Descobri recentemente uma boa ferramenta para medir o desempenho dos vários algos disponíveis: http://www.dmi.unict.it/~faro/smart/index.php

Você pode achar util. Além disso, se eu precisasse atender rapidamente o algoritmo de pesquisa de substring, usaria Knuth-Morris-Pratt.

Você também pode querer ter diversos benchmarks com vários tipos de strings, pois isso pode ter um grande impacto no desempenho. Os algos terão desempenho diferenciado com base na pesquisa de linguagem natural (e mesmo aqui ainda pode haver distinções refinadas por causa das diferentes morfologias), seqüências de DNA ou seqüências aleatórias etc.

O tamanho do alfabeto terá um papel importante em muitos algos, assim como o tamanho da agulha. Por exemplo, Horspool faz bem no texto em inglês, mas prejudica o DNA por causa do tamanho diferente do alfabeto, dificultando a vida da regra dos caracteres ruins. A introdução do sufixo bom alivia muito isso.

Não sei se é o melhor, mas tive uma boa experiência com Boyer-Moore .

Isso não responde diretamente à pergunta, mas se o texto for muito grande, que tal dividi-lo em seções sobrepostas (sobreposição pelo comprimento de um padrão), procure simultaneamente as seções usando threads. No que diz respeito ao algoritmo mais rápido, Boyer-Moore-Horspool, acho que é um dos mais rápidos, senão o mais rápido, entre as variantes de Boyer-Moore. Publiquei algumas variantes de Boyer-Moore (não sei o nome delas) neste tópico Algoritmo mais rapidamente que a pesquisa BMH (Boyer-Moore-Horspool) .

O mais rápido atualmente é o EPSM, de S. Faro e OM Kulekci. Veja http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

"Correspondência exata de sequência compactada" otimizada para SIMD SSE4.2 (x86_64 e aarch64). Ele executa estável e melhor em todos os tamanhos.

O site ao qual eu vinculei compara 199 algoritmos de pesquisa rápida em cadeia, com os usuais (BM, KMP, BMH) sendo bastante lentos. O EPSM supera todos os outros aqui mencionados nessas plataformas. Também é o mais recente.