Estoy buscando un algoritmo para el cual la implementación esté fácilmente disponible en C. Mi entrada consiste en muchos patrones y muchos textos. Quiero encontrar la primera aparición de cada patrón en cada uno de los textos.
Estoy explorando algoritmos de coincidencia de cadenas desde aquí: http://igm.univ-mlv.fr/~lecroq/string/
Pero no estoy seguro de la mejor solución posible. ¿Alguien sabe el mejor algoritmo de coincidencia para este caso de uso?
Mis patrones estarán en el rango de 10-15 caracteres y los textos estarán en el rango de 30-40 caracteres.
También se mencionan algunas de las respuestas de stackoverflow.que Boyes-Moore y KMP no se desempeñan necesariamente mejor que strstr () debido a las arquitecturas modernas de HW. ¿Será eso cierto para mi caso de uso peculiar también?
Aquí hay otra lista de algoritmos. http://www.dmi.unict.it/~faro/smart/algorithms.php
Respuestas
0 para la respuesta № 1Usar modificacion de el algoritmo de Rabin-Karp:
Calcule la longitud mínima del patrón para sus patrones (10 en su ejemplo)
Para cada patrón, crea "hash-serpiente" con el prefijo longitud = 10. Crea hashtable para tus patrones.
Para cada texto, "mueve la longitud de la serpiente = 10", y vuelve a calcular el hash. Si hash coincide con cualquier prefijo - compara la cadena completa.
Entonces, este algoritmo es ~ O (n + m); N = longitud de los textos; M = longitud de patrones.
Para el hashing, recomiendo usar el par "cyclic_shift + XOR".