¿Cómo encontrar la subcadena común más larga usando árboles?
El problema más largo de subcadenas comunes según wiki se puede resolver utilizando un árbol de sufijos.
Desdewiki:
Las subcadenas comunes más largas de un conjunto de cadenas se pueden encontrar al construir un árbol de sufijos generalizado para las cadenas, y luego encontrar los nodos internos más profundos que tienen nodos de hoja de todas las cadenas en el subárbol que se encuentra debajo.
No entiendo esto
Ejemplo: si tengo:ABCDE
yXABCZ
entonces el árbol del sufijo es (algunas ramas deXABCZ
omitido debido al espacio):
La subcadena común más larga esABC
pero no es así, no puedo ver cómo la descripción de wiki ayuda aquí.ABC
No es el más profundo de los nodos internos con nodos de hoja.
¿Alguna ayuda para entender cómo funciona esto?