El algoritmo Z es una forma eficiente de encontrar todas las ocurrencias de una cadena corta en una cadena larga. Esto se conoce como el problema de coincidencia de cadena exacta.
La manera fácil pero lenta de hacer esto es recorrer todos los caracteres de la cadena larga y ver si hay una cadena corta que comienza con ese carácter.
El algoritmo Z es eficiente porque a medida que se mueve a través de la cadena larga guarda información sobre los prefijos de la cadena corta que encuentra.
- ¿Por qué es importante la condición i + j <n en el siguiente código?
- ¿Habría algún límite matemático potencial para una máquina física con el propósito de replicarse a sí mismo?
- Como programador autodidacta, ¿cómo puedo saber mi nivel?
- Si se le da un gráfico G no dirigido simple, ¿cómo podemos encontrar todas las subgrafías inducidas de G, que son gráficos de girasol, dentro de una cantidad de tiempo polinómica?
- ¿Cuál es el significado y el beneficio de las variables compartidas en Theano?
El tiempo de ejecución del algoritmo Z es [matemática] O (n) [/ matemática], donde [matemática] n [/ matemática] es el tamaño de la cadena larga. Esto se debe a que en cada iteración del algoritmo, avanza un carácter o encuentra a lo sumo una falta de coincidencia. Entonces, el peor tiempo de ejecución es [matemática] O (2n) = O (n) [/ matemática].
Esa es la descripción general de alto nivel. Para obtener más detalles sobre cada paso del algoritmo, no puedo hacer nada mejor que lo que ya existe, y no hay un atajo para comprenderlo que no sea trabajarlo. Le recomendaría que tome un ejemplo de una de las explicaciones y lo escriba en papel. Luego impleméntelo en su idioma favorito.
Algunas fuentes para mirar:
- Con mucha notación matemática y código C: Algoritmo Z – Codeforces
- Resumen de diapositiva, con diagramas: Página en umd.edu
- Ejemplo detallado, con código Python: algoritmo Z | Ivan Yurchenko
- Conferencia en video: página en youtube.com
