Algoritmo para encontrar a primeira ocorrência de cada um dos padrões fornecidos em cada um dos textos de entrada fornecidos - string, algoritmo, correspondência de padrões, substring, string-matching

Eu estou procurando algoritmo para o qual a implementação está prontamente disponível em C. Minha entrada consiste em muitos padrões e muitos textos. Eu quero encontrar a primeira ocorrência de cada padrão em cada um dos textos.

Eu estou explorando algoritmos de correspondência de strings aqui: http://igm.univ-mlv.fr/~lecroq/string/

Mas não tenho certeza da melhor solução possível. Alguém sabe o melhor algoritmo de correspondência para este caso de uso?

Meus padrões estarão na faixa de 10-15 caracteres e textos estarão na faixa de 30-40 caracteres.

Também algumas das respostas do stackoverflow mencionamque o Boyes-Moore & KMP não necessariamente tem um desempenho melhor que o strstr () por causa das arquiteturas modernas de HW. Isso será verdade para meu caso de uso peculiar também?

Aqui está outra lista de algoritmos. http://www.dmi.unict.it/~faro/smart/algorithms.php

Respostas:

Use modificação de o algoritmo de Rabin-Karp:

1. Calcule o tamanho mínimo do padrão para seus padrões (10 no seu exemplo)

2. Para cada padrão, crie "snake-hash" com tamanho de prefixo = 10. Crie hashtable para seus padrões.

3. Para cada texto, "move snake length = 10" e recompute o hash. Se hash corresponder a um prefixo - compare a string completa.

Então, esse algoritmo é ~ O (n + m); N = comprimento dos textos; M = comprimento patterls.

Para hashing, eu recomendo usar o par "cyclic_shift + XOR".