string - ¿Cuándo usar los algoritmos Rabin-Karp o KMP?

rabin karp algorithm

Question

He generado una cadena usando el siguiente alfabeto. {A,C,G,T} . Y mi cadena contiene más de 10000 caracteres. Estoy buscando los siguientes patrones en ella.

• ATGGA
• TGGAC
• CCGT

He solicitado utilizar un algoritmo de coincidencia de cadenas que tenga un tiempo de ejecución de O(m+n) .

m = pattern length
n = text length

Los KMP and Rabin-Karp algorithms tienen este tiempo de ejecución. ¿Cuál es el algoritmo más adecuado (entre Rabin-Carp y KMP) en esta situación?

Answer 1

Cuando desea buscar múltiples patrones, normalmente la opción correcta es utilizar Aho-Corasick , que es una generalización de KMP . Ahora, en su caso, solo está buscando 3 patrones, por lo que puede ser que KMP no sea mucho más lento (como máximo tres veces), pero este es el enfoque general.

Rabin-Karp es más fácil de implementar si asumimos que nunca ocurrirá una colisión, pero si el problema que tiene es una búsqueda de cadenas típica, KMP será más estable sin importar la información que tenga. Sin embargo, Rabin-Karp tiene muchas otras aplicaciones, donde KMP no es una opción.