Problema de la subcadena repetida más larga

En informática , el problema de la subcadena repetida más larga consiste en encontrar la subcadena más larga de una cadena que aparezca al menos dos veces.

Este problema se puede resolver en tiempo y espacio lineales.${\displaystyle \Theta (n)}$construyendo un árbol de sufijos para la cadena (con un símbolo especial de fin de cadena como '$' añadido) 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 recorridos desde la raíz. La cadena formada por las aristas 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${\displaystyle k}$Las ocurrencias se pueden resolver preprocesando primero el árbol para contar el número de descendientes de hoja para cada nodo interno, y luego encontrando el nodo más profundo con al menos${\displaystyle k}$descendientes de hojas. Para evitar repeticiones superpuestas, puede comprobar que la lista de longitudes de sufijos no tenga elementos consecutivos con una diferencia menor que la longitud del prefijo.

En la figura con la cadena "ATCGATCGA$", la subcadena más larga que se repite al menos dos veces es "ATCGA".

• Allison, L. "Árboles de sufijos" . Recuperado el 14 de octubre de 2008 .
• Implementación en C de la subcadena repetida más larga utilizando un árbol de sufijos.
• Demostración en línea: Subcadena repetida más larga