árbol palíndromo

En informática, un árbol palíndromo , también llamado EerTree, ^{[ 1 ]} es un tipo de árbol de búsqueda que permite un acceso rápido a todos los palíndromos contenidos en una cadena . Se pueden usar para resolver el problema de la subcadena palíndroma más larga , el problema de la k -factorización ^{[ 2 ]} (¿se puede dividir una cadena dada en exactamente k palíndromos?), la longitud palíndroma de una cadena ^{[ 3 ]} (¿cuál es el número mínimo de palíndromos necesarios para construir la cadena?) y encontrar y contar todos los subpalíndromos distintos. Los árboles palíndromos hacen esto de manera en línea , es decir, no requieren la cadena completa al principio y se pueden agregar carácter por carácter.

Descripción

Ejemplo de árbol palíndromo para TACOCAT, donde las líneas continuas representan los bordes de los caracteres y las líneas discontinuas los bordes de los sufijos.

Como la mayoría de los árboles, un árbol palíndromo consta de vértices y aristas dirigidas . Cada vértice representa un palíndromo (por ejemplo, 'tacocat'), pero solo almacena su longitud, y cada arista representa un carácter o un sufijo . Las aristas de caracteres indican que, al añadir el carácter a ambos extremos del palíndromo representado por el vértice de origen, se crea el palíndromo en el vértice de destino (por ejemplo, una arista con la letra 't' conectaría el vértice de origen 'acoca' con el vértice de destino 'tacocat'). La arista de sufijo conecta cada palíndromo con el sufijo palíndromo más largo que posee (en el ejemplo anterior, 'tacocat' tendría una arista de sufijo con 't', y 'atacocata' tendría una arista de sufijo con 'ata'). La diferencia entre los árboles palíndromos y los árboles regulares radica en que tienen dos raíces (ya que, de hecho, son dos árboles separados). Las dos raíces representan palíndromos de longitud -1 y 0. Es decir, si se añade el carácter 'a' a ambas raíces, el árbol producirá 'a' y 'aa' respectivamente. Dado que cada arista añade (o elimina) un número par de caracteres, los dos árboles solo se conectan mediante aristas de sufijo.

Operaciones

Agregar

Dado que un árbol de palíndromos sigue una construcción en línea, mantiene un puntero al último palíndromo añadido. Para añadir el siguiente carácter al árbol, add(x)primero se comprueba si el primer carácter anterior al palíndromo coincide con el carácter que se va a añadir. Si no coincide, se siguen los enlaces de sufijo hasta que se pueda añadir un palíndromo al árbol. Una vez encontrado un palíndromo, si ya existía en el árbol, no hay que hacer nada. En caso contrario, se añade un nuevo vértice con un enlace desde el sufijo hasta el nuevo vértice, y se añade un enlace de sufijo para el nuevo vértice. Si la longitud del nuevo palíndromo es 1, el enlace de sufijo apunta a la raíz del árbol de palíndromos que representa una longitud de -1.

# S -> Cadena de entrada # x -> posición en la cadena del carácter que se está agregando def add ( x : int ) -> bool : """Agrega el carácter al árbol palíndromo.""" while True : if x - 1 - current . length >= 0 and S [ x - 1 - current . length ] == S [ x ]: break current = current . suffixSi current.add [ S [ x ] ] no es None : devolver Falsesufijo = actual actual = Palindrome_Vertex () actual . longitud = sufijo . longitud + 2 sufijo . agregar [ S [ x ]] = actualSi current.length == 1 : current.suffix = root , devolver TrueMientras sea verdadero : sufijo = sufijo.sufijo si x - 1 - sufijo.longitud > = 0 y S [ x - 1 - sufijo.longitud ] == S [ x ] : actual.sufijo = sufijo.agregar [ S [ x ] ] retornar verdadero

Árboles conjuntos

Encontrar palíndromos que sean comunes a varias cadenas o únicos para una sola cadena se puede hacer con $O(n*i)$ espacio adicional donde $i$ es el número de cadenas que se comparan. Esto se logra agregando una matriz de longitud $i$ a cada vértice y estableciendo la bandera en 1 en el índice $i$ si se alcanzó ese vértice al agregar la cadena $i$ La única otra modificación necesaria es restablecer el puntero actual a la raíz al final de cada cadena. Al unir árboles de esta manera, se pueden resolver los siguientes problemas:

Número de palíndromos comunes a todas las cadenas
Número de palíndromos únicos en una cadena
El palíndromo más largo común a todas las cadenas
El número de palíndromos que aparecen con más frecuencia en una cadena que en otras.

Complejidad

Tiempo

Construir un árbol palíndromo lleva $O(n\log {\sigma })$ tiempo, donde $n$ es la longitud de la cuerda y $\sigma$ es el tamaño del alfabeto. Con $n$ llamadas a add(x), cada llamada tarda $O(\log {\sigma })$ tiempo amortizado . Esto es resultado de que cada llamada add(x)aumenta la profundidad del vértice actual (el último palíndromo en el árbol) en como máximo uno, y la búsqueda de todos los posibles bordes de caracteres de un vértice toma $O(\log {\sigma })$ tiempo. Al asignar el costo de moverse hacia arriba y hacia abajo del árbol a cada llamada a add(x), el costo de moverse hacia arriba del árbol más de una vez se "paga" con un número igual de llamadas a add(x)cuando no se produjo el movimiento hacia arriba del árbol.

Espacio

Un árbol palíndromo toma $O(n)$ espacio: como máximo $n+2$ vértices para almacenar los subpalíndromos y dos raíces, $n$ bordes, que unen los vértices y $n+2$ bordes de sufijo.

compensación espacio-tiempo

Si en lugar de almacenar solo los bordes adicionales que existen para cada palíndromo, se utiliza una matriz de longitud $\sigma$ Los bordes se almacenan, encontrar el borde correcto se puede hacer en tiempo constante, lo que reduce el tiempo de construcción a $O(n+p*\sigma )$ mientras aumenta el espacio para $O(p*\sigma )$ , dónde $p$ es el número de palíndromos.

Referencias

↑ Rubinchik, Mikhail; Shur, Arseny M. (2015). "Eertree: una estructura de datos eficiente para procesar palíndromos en cadenas". European Journal of Combinatorics . arXiv : 1506.04862v1 .
↑ Galil, Zvi; Seiferas, Joel (1978). "Un algoritmo de reconocimiento en línea de tiempo lineal para Palstar " . Journal of the ACM . 25 (1): 102–111 . doi : 10.1145/322047.322056 . S2CID 41095273 .
↑ Fici, Gabriele; Gagie, Travis; Kärkkäinen, Juha; Kempa, Dominik (2014). "Un algoritmo subcuadrático para la factorización palindrómica mínima" . Revista de algoritmos discretos . 28 : 41– 48. arXiv : 1403.2431 . doi : 10.1016/j.jda.2014.08.001 . S2CID 14871164 .

[MR&AS-1] Rubinchik, Mikhail; Shur, Arseny M. (2015). "Eertree: una estructura de datos eficiente para procesar palíndromos en cadenas". European Journal of Combinatorics . arXiv : 1506.04862v1 .

[kfactor-2] Galil, Zvi; Seiferas, Joel (1978). "Un algoritmo de reconocimiento en línea de tiempo lineal para Palstar " . Journal of the ACM . 25 (1): 102–111 . doi : 10.1145/322047.322056 . S2CID 41095273 .

[plength-3] Fici, Gabriele; Gagie, Travis; Kärkkäinen, Juha; Kempa, Dominik (2014). "Un algoritmo subcuadrático para la factorización palindrómica mínima" . Revista de algoritmos discretos . 28 : 41– 48. arXiv : 1403.2431 . doi : 10.1016/j.jda.2014.08.001 . S2CID 14871164 .

[ 1 ]

[ 2 ]

[ 3 ]