Subtrucción de palíndromos más largos en complejidad de tiempo de ejecución logarítmica

Question

En un palíndromo de tamaño N, la cantidad de candidatos para el palíndromo más largo es n ^ 2.Por lo tanto, el límite inferior teórico de la información (IBT) debe ser LG (n ^ 2), que es equivalente a una complejidad de tiempo de ejecución de LG (N).

Por iBT quiero decir que si usamos un algoritmo basado en comparación y usted piensa en un árbol de decisiones para aplicarlo, las hojas de ese árbol serán todas las posibilidades (n ^ 2 hojas), por lo tanto, la altura de ese árboles lg (n ^ 2).Sin embargo, no pude encontrar ningún algoritmo que sea capaz de resolver esta pregunta en esta complejidad de tiempo de ejecución;Lo mejor que he encontrado es el algoritmo de Manacher que resuelve la pregunta en el tiempo lineal.

Answer 1

Si se le da un palíndromo $ p $ de tamaño $ n $ (como usted diceAl comienzo de la pregunta), entonces el palíndromo más largo es $ p $ en sí mismo y no necesita hacer ningún cálculo.

Si su entrada no es un palíndromo, sino una cadena arbitraria, entonces necesita al menos leer la entrada y, por lo tanto, $ \ omega (n) $ es un triviallímite inferior.