Algoritmos de búsqueda de cadenas

Question

Para los dos algoritmos de búsqueda de cadenas: KMP y árbol de sufijos, ¿cuál es el preferido en qué casos? Da algunos ejemplos prácticos.

Answer 1

árbol Un sufijo es mejor si usted tendrá que responder a muchas preguntas tales como "es la aguja presente en el pajar?". KMP es mejor si solo tiene que buscar una cadena en otra cadena y no tener que hacerlo muchas veces.

Un árbol de sufijos es una estructura de datos mucho más general, por lo que se puede hacer mucho más con ella. Vea lo que puede hacer con él here. KMP es útil para encontrar si una cadena es una subcadena en otra cadena.

Es posible que también desee comprobar otros algoritmos, como Boyer-Moore, Rabin-Karp e incluso el algoritmo ingenuo, ya que hay situaciones (entradas) en las que una es mejor que las demás.

El fondo es:

1. Si usted tiene una gran cantidad de consultas como la que he mencionado anteriormente, vale la pena construir un árbol de sufijos y luego responder a cada consulta rápida.
2. Si necesita hacer más que ese tipo de consultas, también vale la pena construir un árbol de sufijos.
3. Si solo le preocupa ocasionalmente encontrar si una cadena es una subcadena de otra cadena, entonces use KMP.