Algoritmo del administrador

Algoritmo del administrador
objetivo	Buscar subpalíndromos
Estructura de datos	Línea
peor momento	$En)$
costo de memoria	$En)$

El algoritmo de Manacher es un algoritmo con tiempo de ejecución lineal que le permite obtener información sobre todas las subcadenas palindrómicas de una cadena dada en forma comprimida . Introducido por Glenn Manaker en 1975. La tarea inicial resuelta por el algoritmo era encontrar el prefijo-palíndromo más pequeño de una cadena dada, pero la estructura obtenida como resultado de la operación del algoritmo permite resolver problemas más generales. Entonces, Manaker demostró que el algoritmo le permite verificar si una cadena se puede representar en la forma , donde , alguna cadena , es su inversión. En 1995, Apostolico, Breslauer y Galil señalaron que, por diseño, el algoritmo de Manaker no solo encuentra el prefijo palindrómico más corto, sino que también encuentra el radio palindrómico máximo para cada centro posible de una subcadena palindrómica. ${\ estilo de visualización (\ omega \ omega ^{R})^{k}}$ $\omega$ ${\ estilo de visualización \ omega ^ {R}}$

Planteamiento del problema

Sea una cuerda . Su inversión es una cadena compuesta por los mismos caracteres, pero escrita en orden inverso. ${\ estilo de visualización \ omega = \ omega _ {1} \ omega _ {2} \ puntos \ omega _ {n}}$ ${\ estilo de visualización \ omega ^ {R} = \ omega _ {n} \ puntos \ omega _ {2} \ omega _ {1}}$
Una cadena se llama palíndromo si , es decir, si se lee igual de izquierda a derecha y de derecha a izquierda. $\omega$ ${\displaystyle \omega =\omega ^{R))$
Se dice que un palíndromo es par si tiene una longitud par e impar en caso contrario. Cualquier palíndromo par tiene la forma , y un palíndromo impar tiene la forma , donde es un carácter arbitrario. $\omega$ ${\displaystyle \omega =vv^{R))$ ${\displaystyle \omega =vav^{R))$ $a$
La cuerda tiene un palíndromo de radio uniforme centrado en la posición si para . En consecuencia, la cuerda tiene un palíndromo de radio impar centrado en si para . $\omega$ $r$ $k$ ${\ estilo de visualización \ omega _ {ki} = \ omega _ {k + i-1}}$ ${\ estilo de visualización i = 1, \ puntos, r}$ $r$ $k$ ${\ estilo de visualización \ omega _ {ki} = \ omega _ {k + i}}$ ${\ estilo de visualización i = 1, \ puntos, r}$

Se dice que un radio es máximo para una posición si la cuerda no tiene un palíndromo con un radio centrado en la misma posición. $r$ $k$ $r+1$

El algoritmo de Manaker te permite encontrar en tiempo lineal los radios máximos de los palíndromos pares e impares en cada posición de la cuerda . $k=1,\puntos,n$ $\omega$

Implementación

A continuación se muestra la implementación del algoritmo en Python .

def manager_odd ( s ): s = '$' + s + '^' n = len ( s ) res = [ 0 ] * n l = 0 r = 0 for i in range ( 1 , n - 1 ): res [ i ] = max ( 0 , min ( r - i , res [ l + ( r - i )])) while s [ i - res [ i ]] == s [ i + res [ i ]]: res [ i ] += 1 si i + res [ i ] > r : l = i - res [ i ] r = i + res [ i ] return res [ 1 : - 1 ] def manacher ( s ): res = manacher_odd ( '#' + '#' . join ( s ) + '#' )[ 1 : - 1 ] return ([ x // 2 for x in res [:: 2 ]] , [ x // 2 para x en resolución [ 1 :: 2 ]])

La función manacher_odddevuelve una matriz Manaker para palíndromos de longitud impar, la función manacherdevuelve un par de matrices Manaker para palíndromos de longitudes pares e impares, respectivamente, reduciendo el cálculo de una matriz para longitudes pares a un caso impar al agregar un carácter de servicio #.

Literatura

Manacher G. K. Un nuevo algoritmo "en línea" de tiempo lineal para encontrar el palíndromo inicial más pequeño de una cadena // J. ACM / D. J. Rosenkrantz - Nueva York, NY : Association for Computing Machinery , 1975. - Vol. 22, edición. 3.- Págs. 346-351. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Detección paralela de todos los palíndromos en una cadena (inglés) // Ciencias informáticas teóricas - Elsevier BV , 1995. - Vol. 141, edición. 1-2. - Pág. 163-173. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(94)00083-U

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitudes Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común