A continuación se muestra un posible algoritmo. Es tan simple escribir el código real de Python como casi un seudocódigo. Este algoritmo es ingenuo y no se garantiza que se ejecute en tiempo lineal como el algoritmo de Manacher. Es lo suficientemente rápido para casos no patológicos (como palíndromos incrustados en palíndromos).
La idea es verificar la presencia de un palíndromo que comience con su letra central. Hacemos esto porque la letra central es el único punto de inicio estable ya que ignoramos el tamaño del palíndromo que estamos buscando.
Hay una pequeña trampa: tenemos que distinguir entre el tamaño impar y el palíndromo de tamaño par. El palíndromo de tamaño impar siempre se encontrará porque una letra única ya es un palíndromo. Por otro lado, los palíndromos de tamaño uniforme solo existen si coinciden dos letras consecutivas.
- ¿Cuáles son algunas preguntas de la entrevista para verificar las habilidades de gestión?
- ¿Qué rango de salario debe pedir un desarrollador de React durante una entrevista de trabajo?
- ¿Cuál es la mejor respuesta a la pregunta de reclutamiento sobre mi mayor logro?
- ¿Cuáles son los consejos no obvios pero útiles para la parte de diseño de producto de las entrevistas de PM de Google?
- ¿Cuál es la mejor guía para pasar una entrevista de trabajo?
En ambos casos, simplemente tenemos que verificar si las letras coinciden con el gasto de nuestro punto central elegido.
Verificar los límites es fácil: sabemos desde el principio la posición de la letra central y la longitud de la cadena, de lo que podemos deducir el tamaño del palíndromo máximo posible si todas las letras coinciden.
A continuación se muestra el código de Python.
def pal_at_n(s, n):
"""
Find the largest Palindrome
whose center letter is at position n in input string
"""
# Check for odd sized palindroms (with a central letter)
# rodd will be halfsize + 1 (to fix unmatched central letter)
# odd sized palindrome always exist. One letter is a palindrome
rodd = min(n, len(s)-n-1) + 1
for i in range(0, rodd):
if s[ni] != s[n+i]:
rodd = i
break;
# Check for even sized palindroms (without a central letter)
# reven will be halfsize (can be empty string palindrome)
reven = min(n, len(s)-n-2) + 1
for i in range(0, reven):
if s[ni] != s[n+i+1]:
reven = i
break;
#Keep longest odd or even palindrome
if 2*reven > 2*rodd-1:
return s[n-reven+1:n+reven+1]
else:
return s[n-rodd+1:n+rodd] test_string = "abcdefgracecarkfglerts"
s = "abcdefgracecarkfglertsdefgtraceecartkfglerts"
for pos in range(0, len(s)):
print (pal_at_n(s, pos))
def pal_at_n(s, n):
"""
Find the largest Palindrome
whose center letter is at position n in input string
"""
# Check for odd sized palindroms (with a central letter)
# rodd will be halfsize + 1 (to fix unmatched central letter)
# odd sized palindrome always exist. One letter is a palindrome
rodd = min(n, len(s)-n-1) + 1
for i in range(0, rodd):
if s[ni] != s[n+i]:
rodd = i
break;
# Check for even sized palindroms (without a central letter)
# reven will be halfsize (can be empty string palindrome)
reven = min(n, len(s)-n-2) + 1
for i in range(0, reven):
if s[ni] != s[n+i+1]:
reven = i
break;
#Keep longest odd or even palindrome
if 2*reven > 2*rodd-1:
return s[n-reven+1:n+reven+1]
else:
return s[n-rodd+1:n+rodd] test_string = "abcdefgracecarkfglerts"
s = "abcdefgracecarkfglertsdefgtraceecartkfglerts"
for pos in range(0, len(s)):
print (pal_at_n(s, pos))
Por supuesto, podemos hacer esa búsqueda mucho más rápido si establecemos un tamaño mínimo para los palíndromos que estamos buscando. Eso eliminará rápidamente los partidos imposibles. Aún así, la verificación final tendría que hacerse comparando todas las letras como se indicó anteriormente.