- Crea un trie que contenga filas de tu patrón.
Esto también mostrará inmediatamente la situación en la que varias filas son idénticas. Solo guarde una copia de cada fila distinta. Por ejemplo, si este es el patrón:abacá bacad abacá efefe
el trie contendrá tres registros diferentes: 1 = abacá, 2 = bacad y 3 = efefe. El patrón original ahora corresponde a la secuencia de filas (1,2,1,3).
- Use el trie para construir el autómata finito para el algoritmo Aho-Corasick (la generalización de KMP a múltiples patrones).
- Para cada fila de la matriz, ejecute Aho-Corasick. Para cada celda de la matriz, escriba el número del patrón de fila que termina allí, o 0 si no existe dicho patrón. (Tenga en cuenta que, dado que todos los patrones de nuestro trie son distintos y tienen la misma longitud, hay como máximo una coincidencia en cada celda).
- Para cada columna de la matriz, ejecute KMP y busque la secuencia de números que corresponde a nuestro patrón. Por ejemplo, para el patrón de ejemplo anterior, una coincidencia corresponde a la secuencia de números (1,2,1,3) que aparecen consecutivamente en alguna columna de las notas que tomamos en el paso anterior.
La complejidad temporal de esta solución es óptima: se garantiza que sea lineal en el tamaño de la entrada.
- ¿Qué es un algoritmo para programar un torneo para que termine en el menor tiempo posible, dado un torneo round robin (donde cada jugador juega entre sí) entre n jugadores (n es par) que puede representarse con un gráfico completo?
- Cómo planificar 1-2 años de programación para convertirse en un experto en algoritmos, suponiendo que tenga un conocimiento de C ++ en la escuela secundaria
- ¿Qué significa importar en Python? ¿Puedo hacer mi propio algoritmo sin usar importar?
- ¿Cómo funcionan los algoritmos de YouTube?
- ¿Es posible hackear usando el lenguaje de programación C?
