¿Existe un algoritmo para verificar si una cadena es una catenación de palíndromos?

¿Existe un algoritmo de tiempo lineal para verificar que una secuencia de caracteres es una concatenación de palíndromos? Lo único que me viene a la mente es la solución ingenua:

1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

Nota: la respuesta es trivialmente sí si las cadenas de longitud 1 se definen como palíndromos. Asumamos que este no es el caso.

algorithms efficiency strings saadtaame
fuente

Si está permitiendo palíndromos triviales de longitud 1 (por ejemplo, la cadena "a" es un palíndromo), entonces todas las cuerdas son concatenaciones de palíndromos.

Matt Lewis

¿Es útil o un ejercicio?

Jan Hudec

@MattLewis Puede intentar minimizar la cantidad de palíndromos. Jan, por qué? Suena como un buen ejercicio en programación dinámica.

Pål GD

@Haile No. Solo palíndromos disjuntos.

saadtaame

Norvig hizo un trabajo extenso en Palindromes. Te puede interesar esta página: norvig.com/palindrome.html

robowolverine

Respuestas:

Suponiendo que desea palíndromos disjuntos, esto se conoce como el problema PALSTAR, y hay un algoritmo de tiempo lineal de Zvi Galil y Joel Seiferas. Algoritmo de reconocimiento en línea de tiempo lineal para `` Palstar '' .

Puede encontrar una explicación del algoritmo en el libro aquí: Algoritmos de texto (consulte la página vinculada y las páginas anteriores).

Si está de acuerdo con un algoritmo de tiempo cuadrático, la programación dinámica directa parece funcionar.

Dada una cadena , mantenemos una matriz que nos dice si puede descomponerse en palíndromos. $s[1,\dots n]$ $s[1,\dots j]$

También mantenemos una tabla 2D que nos dice si es un palíndromo o no. Esto lo podemos construir en el tiempo eligiendo un centro y moviendo dos punteros hacia afuera, buscando palíndromos con ese centro. Haga esto para cada centro posible: centros, cada uno tomando tiempo . $s[i, \dots j]$ $O(n^2)$ $\Theta(n)$ $O(n)$

Ahora, puede verificar si puede descomponerse en palíndromos, verificando para cada si puede descomponerse, y si es un palíndromo (usando la tabla 2D anterior). Esto produce un algoritmo tiempo y espacio. $s[1, \dots j+1]$ $1 \le i \le j-1$ $s[1,\dots i]$ $s[i+1,\dots, j+1]$ $\Theta(n^2)$ $\Theta(n^2)$

El uso de espacio puede ser llevado hacia abajo a , si se utiliza de Manacher algoritmo en línea para calcular si es un palíndromo (como va de a ) , básicamente deshacerse de la tabla 2D. $O(n)$ $s[i+1,\dots j+1]$ $i$ $j-1$ $1$

Aryabhata
fuente

Esto es similar a mi algoritmo, simplemente no expliqué la parte de preprocesamiento para dejarlo como ejercicio a OP, pero no sé por qué a nadie le importaba mi algoritmo :)

@SaeedAmiri: ¿Has leído la primera parte de mi respuesta que menciona el tiempo lineal? Como es similar por cierto, OP cambió la pregunta para pedir un algoritmo de tiempo lineal, lo que hace que su respuesta y la segunda mitad de mi respuesta sean irrelevantes. No eliminé esa parte de mi respuesta, porque quería mencionar el algoritmo de Manacher que hace que el algoritmo de programación dinámica solo use el espacio O (n) (y se deshaga del paso de preprocesamiento), y aún podría ser relevante para otras personas que se encuentra con esta pregunta

Aryabhata

No tome la serie, es una broma, me gustan sus respuestas en general, creo que hay un problema con mi escritura en inglés, porque OP no entendió mi solución, y no estaba de humor para dibujarla por imagen . Pero un buen punto OP cambió su pregunta recientemente, y puede haber una solución similar al algoritmo de Manacher (pero realmente no es fácil).

@SaeedAmiri: Ya veo, no te preocupes entonces :-)

Aryabhata

Si se permite la superposición, se puede hacer en tiempo lineal (en el tamaño de la cadena de entrada).

Algunas definiciones

Definamos el concepto de palíndromo máximo :

Un palíndromo máximo de radio k de una cadena S es una subcadena S 'tal que

comenzando desde el centro, S 'lee los mismos k caracteres en ambas direcciones
pero no para k + 1 caracteres
k> 1 (por lo que un solo personaje no es un palíndromo)

por ejemplo, si S = banana, entonces S' = ananaes un palíndromo máximo de radio 2.

Un palíndromo máximo es un palíndromo máximo de radio k para algunos k.

Por ejemplo, si S = banana, "ana", "anana", son todos los palíndromos sus máximos.

Usando palíndromos máximos

Ahora, si pudiéramos localizar todos los palíndromos máximos de una cadena , sería simple verificar si toda la cadena es una concatenación de palíndromos.

Tomar S = abbaccazayaz. Sus palíndromos máximos son:

abba, centrado entre las posiciones 2 y 3, radio = 2
acca, centrado entre las posiciones 5 y 6, radio = 2
zayaz, centrado en la posición 10, radio = 2

entonces "abba" abarca más de [1..4], "acca" abarca más de [4..7], "zayaz" abarca más de [8..12]. Dado que la concatenación de estos tres palíndromos (¿se permite la superposición?) Se extiende por toda la cadena, se deduce que "abbaccazayaz" es la concatenación de palíndromos.

Calcular palíndromos máximos en tiempo lineal

¡Ahora resulta que podemos localizar todos los palíndromos máximos de una cadena S en tiempo lineal !*

La idea es utilizar un árbol de sufijos para S equipado con consultas de antepasados comunes más bajas en tiempo constante .

Entonces podemos verificar si una cadena S de longitud m es una concatenación de palíndromos en el tiempo O (n).

* Gusfield, Dan (1997), "9.2 Encontrar todos los palíndromos máximos en tiempo lineal", Algoritmos sobre cuerdas, árboles y secuencias

Haile
fuente

Suponiendo que se permiten palíndromos superpuestos y que estamos buscando la secuencia de palíndromo más pequeña, no veo por qué esto debería devolver la más pequeña (aunque no tengo un contraejemplo). Si estamos verificando si es posible con palíndromos de radio de al menos , entonces es realmente útil. Además, no es un palíndromo, supongo que querías decir en su lugar.

k

$k$ nanaanana

Khaur

Editado la cosa "anana", gracias. Además, OP no solicita una secuencia mínima de palíndromos: dado que un solo carácter no es un palíndromo, solo tenemos que decidir si la cadena de entrada es una concatenación de palíndromos o no.

Haile

Los caracteres individuales son palíndromos (aunque no sean interesantes). Si supone que no lo están, está resolviendo el segundo problema que menciono para . En una nota de complejidad, después de calcular todos los palíndromos máximos, aún debe verificar que abarquen toda la secuencia, lo que IIRC toma tiempo loglineal en el número de palíndromos (que puede ser casi tan alto como la longitud de la secuencia en casos patológicos) . De todos modos, creo que debería enfatizar más que suponga que se permite la superposición, ya que no es una suposición tan obvia.

k = 1

$k=1$

Khaur

@Khaur Solo toma tiempo loglineal si los intervalos no están ordenados. En este caso, probablemente lo sean.

Yuval Filmus

En los comentarios a la pregunta, el OP agrega explícitamente que los palíndromos superpuestos no están permitidos. Entonces, esta solución en forma actual no es lo que el OP está buscando. Creo que esta solución también se puede modificar para resolver el caso no superpuesto, con un poco de reflexión y una complejidad casi cuadrática. Pero no lo he pensado mucho.

Paresh

Suponga que Palindrome [] [] es una matriz y Palindrome (i, j) es una función que verifica si la subcadena de i a j es palindrome y devuelve 1 si es palindrome o devuelve infinito si no es palindrome, y está buscando el número más pequeño de particiones, créelo de abajo hacia arriba:

P a l i n d r o m e [i] [i] = 1.

$Palindrome[i][i] = 1.$

\forall 0 \leq i < j < n : P a l i n d r o m e [i] [j] = min {P a l i n d r o m e (i, j), min_{i \leq k < j} {P a l i n d r o m e [i, k] + P a l i n d r o m e [i + 1, k]}}

$\forall 0\le i < j < n : Palindrome[i][j] = \min\{Palindrome(i,j), \min_{i\le k<j} \{Palindrome[i,k] + Palindrome[i+1,k]\}\}$

Debe llenar las celdas y cada celda toma como máximo para que el algoritmo sea , con una pequeña modificación (preprocesamiento) puede mejorarlo a , también Encontrar esta partición no es difícil. $O(n^2)$ $O(n)$ $O(n^3)$ $O(n^2)$

fuente

¿Puedes ilustrar con un ejemplo? Diga:abbaaccaabba.

saadtaame

@saadtaame, OK, aquí no es posible crear una tabla (en cs.stackexchange), o no pude encontrar una manera de hacerlo, lo haré en algún lugar y pondré la imagen aquí más tarde. pero por ahora intenta comprenderlo usted mismo, comience desde las subcadenas de longitud 1, luego verifique los palíndromos de longitud 2 ... y así sucesivamente.