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²).
- ¿Cuáles son algunos problemas de práctica en la estructura de datos de árbol en sitios web competitivos?
- ¿Qué cosas (lenguajes de programación, algoritmos, etc.) aprendió Ashish Kedia después de completar su primer año?
- Cómo entender el análisis amortizado del algoritmo
- ¿Dónde puedo encontrar problemas difíciles de algoritmo / estructura de datos?
- ¿Cómo calcula Google la distancia entre dos lugares en Google Maps?
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).
