¿Cómo podemos encontrar el número de subcadenas palindrómicas en una cadena en tiempo lineal?

Aquí hay una solución O (N log N) usando hashing.

Deje S [1 … N] ser la cadena original. Deje T [N … 1] ser la cadena invertida. En primer lugar, elija un esquema de hash que permita calcular el hash para cualquier subcadena de S y T utilizando solo la precomputación O (N). Una forma sería utilizar el esquema seguido en el algoritmo Rabin-Karp, que se describe aquí. Usando el esquema, precalcule los hashes para todos los prefijos de S y T en el tiempo O (N). Se pueden usar para encontrar el hash directo / inverso para cualquier subcadena en el tiempo O (1).

Ahora, tenga en cuenta que S [i … j] es un palíndromo iff S [i … j] = T [j … i]. Si nuestro esquema de hashing es lo suficientemente bueno, esto sucede si hash (S [i … j]) = hash (T [j … i]). Podemos verificar si el hash para cada subcadena S [i … j] es igual al hash para T [j … i]. Esto llevaría tiempo O (N²).

Pero podemos mejorar esta complejidad usando la búsqueda binaria. S [i … j] es un palíndromo para j-i + 1> 2 si S [i] = S [j] y S [i + 1 … j-1] es un palíndromo. La segunda condición significa que por cada carácter / par de caracteres adyacentes, hay un tamaño máximo de palíndromo que puede centrarse en él. Cada subcadena más corta centrada en ella será un palíndromo, mientras que cada subcadena más larga no lo será. Por ejemplo, considere la cadena ‘zabcdcbef’. Si observamos todas las subcadenas con ‘d’ como centro, ‘d’, ‘cdc’, ‘bcdcb’ son palíndromos, mientras que ‘abcdcbe’ y ‘zabcdcbef’ no lo son. Para cada centro, use la búsqueda binaria para encontrar el palíndromo más largo centrado alrededor de él. Dado que hay centros 2N-1 y realizar una búsqueda binaria toma tiempo O (log N) por centro, la complejidad general es O (N log N).

Además de la solución de árbol de sufijos, hay otra solución lineal que usa
Árbol palindrómico , que es una estructura de datos inventada por MikhailRubinchik – Codeforces y representada durante el Campamento de Verano Petrozavodsk 2014 .

La idea básica es tener un gráfico en forma de árbol donde:
– Cada subcadena palindrómica distinta está representada por un nodo.
– Cada borde del nodo x al nodo y , con el carácter a representa que podríamos construir la subcadena palindrómica del nodo y agregando el carácter a a ambos lados de la subcadena palindrómica del nodo x .
– Enlaces adicionales entre nodos, donde cada enlace adicional del nodo x al nodo y significa que la subcadena palindrómica del nodo y es el palíndromo más grande, que también es sufijo de la subcadena palindrómica de x .

Este blog El árbol palindrómico explica muy bien el árbol palindrómico. Muestra cómo construir un árbol palindrómico en tiempo lineal. También contiene código de muestra para ello.

Después de construir el árbol palindrómico, puede obtener fácilmente el número de subcadenas palindrómicas distintas utilizando el número de nodos.

Esto se puede hacer en tiempo lineal usando árboles de sufijos:
1) Para un alfabeto de tamaño constante, podemos construir árboles de sufijos utilizando el algoritmo de Ukkonen en O (n).
2) Para la cadena S dada, construya un árbol de sufijos generalizado de S # S` donde S ‘es inverso a la cadena S y # está delimitando el carácter.
3) Ahora en este árbol de sufijos, para cada sufijo i en S, busque el ancestro común más bajo del sufijo (2n-i + 1) es S`.
4) cuente todos los sufijos en el árbol para obtener el recuento total de todos los palíndromos.
5) Incluso puedes ir más lejos y obtener el palíndromo más largo. Busque LCA que sea más profundo en el árbol, es decir, cuya distancia desde la raíz sea máxima.

Este algoritmo lleva tiempo lineal (utilizado por Genebank para encontrar palíndromos biológicos en secuencias de ADN), aunque para cadenas muy grandes puede hacer un preprocesamiento de tiempo cuadrático de este árbol para responder consultas LCA en tiempo constante.

La construcción y la búsqueda requieren tiempo lineal. Entonces el tiempo de ejecución sigue siendo O (n).

Un ejemplo:
Cadena dada S = mabbax. A continuación se muestra el árbol de sufijos para la cadena mabbax # xabbam.
El LCA de los sufijos 3 y 11 le dará un palíndromo.

| (1: mabbax # xabbam) | hoja
árbol: |
El | El | | (6: x # xabbam) | hoja
El | | (3: bba) |
El | El | | (13: m) | hoja
| (2: a) |
El | | (6: x # xabbam) | hoja
El | El |
El | | (13: m) | hoja
El |
El | El | | (6: x # xabbam) | hoja
El | | (4: ba) |
El | El | | (13: m) | hoja
| (3: b) |
El | El | | (6: x # xabbam) | hoja
El | | (5: a) |
El | El | | (13: m) | hoja
El |
El | | (7: #xabbam) | hoja
| (6: x) |
El | | (9: abbam) | hoja
El |
| (7: #xabbam) | hoja
7 nodos ramificados

Alternativamente, también puede hacerlo utilizando matrices de sufijos. Para el árbol de sufijos generalizado construido anteriormente, atraviese el árbol lexicográficamente y complete la matriz de sufijos. La matriz de sufijo de paso simple le daría el número total de subcadenas palindrómicas en una cadena original.

Referencia: http://algo2006.csie.dyu.edu.tw/
Documento de Ukkonen: (lo hace manteniendo enlaces de sufijo) http://www.cs.helsinki.fi/u/ukko

Por favor siga este enlace. Tiene una explicación y un código para encontrar la subcadena palindrómica más larga en tiempo lineal. Esto se conoce como el algoritmo de Manacher.

Encontrar la subcadena palindrómica más larga en tiempo lineal

Editar: dado que la pregunta se cambia para encontrar el número de subcadenas palindrómicas, permítame responder esta parte. Cada palíndromo necesita tener un centro. Hay 2 * n-1 centros probables en una cadena de longitud n (cualquier carácter puede ser centro, también el centro puede estar entre dos caracteres). Expande alrededor de cada uno de estos centros. Si los personajes se reflejan alrededor del centro, tenemos una subcadena palindrómica. Incremento del conteo de la subcadena de palíndromo Expanda hasta que se encuentre una falta de coincidencia. Haga esto para todos los centros 2 * n-1. Expandir alrededor de cada centro toma O (n) tiempo. La complejidad general es O (n ^ 2).

referir Algoritmo de Manacher
Subcadena palindrómica más larga Parte II

Utiliza el árbol de palíndromo

More Interesting

¿Se puede ordenar una lista de números en un número menor de pases que el indicado por la notación Big-O?

¿Cuáles son los 5 mejores algoritmos esenciales (excepto la clasificación) que todo programador debe saber?

¿Cuál es el algoritmo más corto para probar si dos cadenas son anagramas?

¿Qué es una explicación intuitiva de bosques aleatorios?

Cómo mejorar mi solución Java para el problema 'nodo de hoja izquierda más profundo en un árbol binario'

¿Qué tan difícil fue crear e implementar el algoritmo de clasificación de página inicial de los primeros Google?

Cómo hacer que el siguiente código sea mejor y más eficiente para el problema de invertir las palabras en la oración dada

Es un método de retroceso para imprimir permutaciones de cadena. No entiendo de qué manera se produce el flujo de control, como después de encontrar el intercambio, el intercambio se llama luego permutar y luego nuevamente. ¿Esto no se me viene a la cabeza?

¿Dónde se usa el algoritmo de Dijkstra?

¿Cómo funciona Swype?

¿En qué se diferencia la programación dinámica del seguimiento hacia atrás?

¿Cuáles son los requisitos previos para Introducción a los algoritmos de Thomas Cormen?

¿Puedo comenzar a aprender visión por computadora sin pasar por algoritmos de aprendizaje automático?

¿Cuáles son algunas aplicaciones prácticas de la teoría de la complejidad y la teoría del caos?

¿Puedo encontrar el camino hamiltoniano más corto en un gráfico completo ponderado no dirigido en tiempo polinómico (donde todos los pesos no son negativos)?