La clave aquí es que podemos iterar las búsquedas a la función de falla. Deje S ser una cadena. Busque la función de falla para que S obtenga el prefijo apropiado más largo S ‘de S, que también es un sufijo. Luego, si busca la función de falla para que S ‘obtenga su prefijo más largo S’ ‘, que también es su sufijo, entonces S’ ‘es el segundo prefijo más largo de la cadena S original que también es un sufijo de S. Y si busca la función de falla para S ”, obtendrá el tercer prefijo apropiado más largo de la cadena original que también es uno de sus sufijos. Y así.
En su ejemplo, la función de falla para toda la cadena es 4, lo que denota que ABAB es el prefijo más largo que también es un sufijo. La cadena de aumento es ABABC, pero su longitud de 5 no divide 9, por lo que no puede ser la subcadena deseada. Entonces, debe continuar buscando la función de falla para ABAB, que le da el siguiente prefijo más largo que también es un sufijo, que es AB. En este caso, la cadena de aumento sería ABABCAB. Nuevamente, 7 no divide a 9, por lo que AB tampoco puede ser la respuesta. Finalmente, buscamos la función de falla de AB, que es 0. Una vez que llegamos a 0, sabemos que la cadena de aumento tiene que ser la cadena completa.
- ¿Qué temas de algoritmos deberían cubrirse para convertirse en un buen programador?
- ¿Cuáles son las ventajas de un árbol AVL?
- ¿Cuál es la diferencia entre un problema formal y solo un problema?
- Cómo implementar un algoritmo usando la recursividad para encontrar el módulo de esta serie
- ¿Cuáles son los mejores libros sobre algoritmos que usan C ++?
