b'\n_START_ARTICLE_\nAlgoritmo de Ukkonen\n_START_SECTION_\nExplicaci\xc3\xb3n del Algoritmo\n_START_PARAGRAPH_\nPara explicar el algoritmo de Ukkonen partiremos de una implementaci\xc3\xb3n ingenua de este algoritmo que es  a la cual se le hacen sucesivas mejoras hasta obtener el ._NEWLINE_Sea  el \xc3\xa1rbol de sufijos impl\xc3\xadcito de la cadena , con  desde  hasta , el algoritmo de Ukkonen aplicado a la cadena  de longitud , construye sucesivamente . La ejecuci\xc3\xb3n del algoritmo de Ukkonen se divide en  fases, en la fase  se construye  modificando , como el \xc3\xbaltimo car\xc3\xa1cter de  es  se cumple que  es el \xc3\xa1rbol de sufijos de ._NEWLINE_Cada fase  es a su vez dividida en  extensiones. En la extensi\xc3\xb3n -\xc3\xa9sima de la fase  se busca el final del camino desde la ra\xc3\xadz etiquetado con la subcadena  y se "extiende" dicho camino con el car\xc3\xa1cter .\n_START_SECTION_\nReglas de extensi\xc3\xb3n\n_START_PARAGRAPH_\nA continuaci\xc3\xb3n se especifica c\xc3\xb3mo se realizan las extensiones. _NEWLINE_Sea  un sufijo de . En la extensi\xc3\xb3n , el algoritmo encuentra el final de  y lo extiende con el car\xc3\xa1cter  de acuerdo a una de las siguientes reglas:_NEWLINE_Regla 1: (Extensi\xc3\xb3n en una hoja)_NEWLINE_El camino de  termina en una hoja. El car\xc3\xa1cter  es a\xc3\xb1adido al final de la etiqueta de la arista incidente en dicha hoja._NEWLINE_Regla 2: (Extensi\xc3\xb3n en una arista o nodo interno)_NEWLINE_El camino de  no termina en una hoja, pero ning\xc3\xban camino desde el final de  inicia con el car\xc3\xa1cter . En este caso una nueva arista etiquetada con  es creada desde el final de , dicha arista incide en una nueva hoja etiquetada con . Si  termina en el interior de una arista, debe crearse adem\xc3\xa1s un nuevo nodo que corte dicha arista en el final de ._NEWLINE_Regla 3: (El car\xc3\xa1cter c ya aparece, no hay que hacer nada)_NEWLINE_Alg\xc3\xban camino desde el final de  inicia con el car\xc3\xa1cter . No es necesario hacer nada.\n_START_SECTION_\nSkip/count trick\n_START_PARAGRAPH_\nCuando se desea buscar la localizaci\xc3\xb3n del final de una cadena  en el \xc3\xa1rbol y se tiene la certeza de que esta se encuentra (como es el caso de las b\xc3\xbasquedas que se realizan en las extensiones), no es necesario machear la cadena  car\xc3\xa1cter a car\xc3\xa1cter, en estos casos es posible utilizar el skip/count trick que permite realizar la b\xc3\xbasqueda en un orden linear respecto al n\xc3\xbamero de nodos del camino._NEWLINE_Sea  el nodo en el que se encuentra el algoritmo, intentando localizar la cadena , el skip/count trick ejecuta sucesivamente el siguiente procedimiento hasta obtener la posici\xc3\xb3n buscada:_NEWLINE_Si S es la cadena vac\xc3\xada, cur es la posici\xc3\xb3n buscada._NEWLINE_Sino (cur,v) es la arista etiqueta L comparte el primer car\xc3\xa1cter con S (tiene que existir y ser \xc3\xbanica)_NEWLINE_    Si |L|<|S|, la posici\xc3\xb3n buscada es el car\xc3\xa1cter |S|-\xc3\xa9simo de la arista (cur,v)._NEWLINE_    Sino hacer cur=v y eliminar los primeros |L| caracteres de S_NEWLINE_Lema: Sea  un suffix link atravesado durante el algoritmo de Ukkonen. En ese momento  est\xc3\xa1 acotada por ._NEWLINE_Demostraci\xc3\xb3n: Cuando el link  (es atravesado, todo nodo interno  ancestro de , con etiqueta  (donde  es un car\xc3\xa1cter y  una cadena posiblemente vac\xc3\xada) tiene un suffix link hacia un nodo , etiquetado con , ancestro de . Esta correspondencia es adem\xc3\xa1s un\xc3\xadvoca. El \xc3\xbanico ancestro que puede tener  sin su correspondiente ancestro para  es la ra\xc3\xadz._NEWLINE_Teorema: Usando el skip/count trick, toda fase del algoritmo de Ukkonen toma un tiempo  donde ._NEWLINE_Demostraci\xc3\xb3n: hay  extensiones en la fase , en una extensi\xc3\xb3n el algoritmo sube en el \xc3\xa1rbol a lo sumo un nodo, atraviesa a lo sumo un suffix link, baja en el \xc3\xa1rbol cierto n\xc3\xbamero de nodos, aplica la extensi\xc3\xb3n y a\xc3\xb1ada a lo sumo un suffix link. Todas las operaciones distintas del descenso en el \xc3\xa1rbol toman tiempo constante. Solo necesitamos analizar la suma de los tiempos de realizar los descensos de todas las extensiones en la fase._NEWLINE_Para ello nos centraremos en la profundidad del nodo  donde el algoritmo termina la fase. Al inicio de la fase se parte de la ra\xc3\xadz, que tiene profundidad , como , en la fase se realizan a lo sumo  descensos de profundidad (cuando se sube al padre o se atraviesa un suffix link), pero la profundidad del  est\xc3\xa1 acotada por , por tanto el n\xc3\xbamero de aumentos de profundidad est\xc3\xa1 acotado por  ya que , y como cada descenso en el \xc3\xa1rbol aumenta la profundidad, el n\xc3\xbamero de descensos en toda la fase est\xc3\xa1 acotado por . Por tanto el tiempo que toma realizar una fase es ._NEWLINE_Corolario: El algoritmo de Ukkonen puede ser implementado usando suffix links en tiempo .\n_START_SECTION_\nExtensiones impl\xc3\xadcitas\n_START_PARAGRAPH_\nObservaci\xc3\xb3n: Una vez que la regla 3 aplica en la extensi\xc3\xb3n  de la fase , la regla 3 aplicar\xc3\xa1 en el resto de las extensiones de la fase . _NEWLINE_Esto es debido a que cuando la regla 3 aplica, es porque la cadena  pertenece al \xc3\xa1rbol antes de realizar la extensi\xc3\xb3n  y por tanto las cadenas  tambi\xc3\xa9n pertenecen al \xc3\xa1rbol, por tanto en las extensiones , la regla 3 tambi\xc3\xa9n aplicar\xc3\xa1._NEWLINE_Observaci\xc3\xb3n: La extensi\xc3\xb3n  crea un suffix link solo cuando en la extensi\xc3\xb3n  aplica la regla 2.\n_START_SECTION_\nStop Trick\n_START_PARAGRAPH_\nEs posible terminar la fase  la primera vez que la regla 3 aplique. Si esto ocurre en la extensi\xc3\xb3n , se dice que las extensiones  se realizaron de forma impl\xc3\xadcita._NEWLINE_Observaci\xc3\xb3n: Sea  la primera extensi\xc3\xb3n de la fase  en la que la regla 3 aplica, se cumple que las primeras  extensiones de la fase  solo pudieron aplicar las reglas 1 o 2. Ambas reglas determinan una hoja etiquetada con el sufijo de  que se extendi\xc3\xb3. En la fase  las primeras  extensiones ocurrir\xc3\xa1n en las hojas determinadas por las primeras j\'-1 extensiones de la fase i. Por tanto en las primeras  extensiones de la fase  aplicar\xc3\xa1 la regla 1._NEWLINE_Observaci\xc3\xb3n: Cuando la regla 1 aplica en la fase , en una hoja , se sustituye la etiqueta  de la arista incidente en la hoja  por . Esto da lugar a la siguiente mejora.\n_START_SECTION_\nPointer Trick\n_START_PARAGRAPH_\nCada vez que una hoja es creada en la fase , se etiqueta la arista incidente a dicha hoja con el par , el pointer trick propone etiquetar dicha arista con el par , donde  es un puntero al n\xc3\xbamero que identifica la fase actual. De esta forma no es necesario hacer nada cuando aplica la regla 1. Como se tiene que las primeras en las primeras  extensiones de la fase  aplicar\xc3\xa1 la regla 1, es posible comenzar la fase  a partir de la extensi\xc3\xb3n , dejando que las primeras  extensiones, se realicen de forma impl\xc3\xadcita._NEWLINE_Teorema: El algoritmo de Ukkonen construye el \xc3\xa1rbol de sufijos de , con los suffix links con costo espacial y temporal ._NEWLINE_Demostraci\xc3\xb3n: El tiempo para realizar todas las extensiones impl\xc3\xadcitas a lo largo del algoritmo es constante._NEWLINE_Consideremos el \xc3\xadndice  correspondiente a la extensi\xc3\xb3n explicita actual, en toda la ejecuci\xc3\xb3n del algoritmo de Ukkonen  nunca decrece, aunque s\xc3\xad se mantiene invariante cuando pasa de una fase a la siguiente._NEWLINE_Como solo hay  fases, el n\xc3\xbamero de extensiones expl\xc3\xadcitas est\xc3\xa1 acotado por . El algoritmo por tanto ejecuta a lo sumo  extensiones expl\xc3\xadcitas. _NEWLINE_Como se explic\xc3\xb3 anteriormente el costo temporal de una extensi\xc3\xb3n expl\xc3\xadcita depende del costo temporal de realizar el descenso en el \xc3\xa1rbol en dicha extensi\xc3\xb3n. Para acotar el n\xc3\xbamero de nodos recorridos en los descensos en el \xc3\xa1rbol durante el algoritmo de Ukkonen, es importante observar, que el nodo actual no var\xc3\xada cuando el algoritmo cambia de fase, la acotaci\xc3\xb3n se efect\xc3\xbaa de forma an\xc3\xa1loga a como se hizo en la demostraci\xc3\xb3n del teorema anterior.'