Problema de subcadena repetido más largo
En ciencias de la computación , el problema de subcadena repetido más largo es el problema de encontrar la subcadena más larga de una cadena que ocurre al menos dos veces.
Este problema se puede resolver en tiempo y espacio lineales construyendo un árbol de sufijos para la cadena (con un símbolo especial de fin de cadena como '$' agregado) y encontrando el nodo interno más profundo en el árbol con más de un hijo. La profundidad se mide por el número de caracteres atravesados desde la raíz. La cadena deletreada por los bordes desde la raíz hasta dicho nodo es una subcadena repetida más larga. El problema de encontrar la subcadena más larga con al menos ocurrencias se puede resolver procesando primero el árbol para contar el número de descendientes de hojas para cada nodo interno, y luego encontrando el nodo más profundo con al menosdescendientes de hojas. Para evitar repeticiones superpuestas, puede verificar que la lista de longitudes de sufijo no tenga elementos consecutivos con una diferencia menor que la longitud de prefijo.
En la figura con la cadena "ATCGATCGA $", la subcadena más larga que se repite al menos dos veces es "ATCGA".
Este artículo relacionado con algoritmos o estructuras de datos es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .
