Después de pasar unas 6-8 horas tratando de digerir el algoritmo de Manacher, estoy listo para tirar la toalla. Pero antes de hacerlo, aquí hay un último disparo en la oscuridad: ¿Alguien puede explicarlo? No me importa el código. Quiero que alguien explique laALGORITMO.

Aquí parece ser un lugar que otros parecían disfrutar al explicar el algoritmo:http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Entiendo por qué querría transformar la cadena, por ejemplo, 'abba' a # a # b # b # a # Después de que estoy perdido. Por ejemplo, el autor del sitio web mencionado anteriormente dice que la parte clave del algoritmo es:

<code>                      if P[ i' ] ≤ R – i,
                      then P[ i ] ← P[ i' ]
                      else P[ i ] ≥ P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])
</code>

Esto parece incorrecto, porque él / ella dice en un punto que P [i] es igual a 5 cuando P [i '] = 7 y P [i] no es menor o igual que R - i.

Si no está familiarizado con el algoritmo, aquí hay algunos enlaces más:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (He intentado este, pero la terminología es horrible y confusa. Primero, algunas cosas no están definidas. También, demasiadas variables. Necesita una lista de verificación para recordar qué variable se refiere a qué).

Otro es:http://www.akalin.cx/longest-palindrome-linear-time (buena suerte)

La esencia básica del algoritmo es encontrar el palíndromo más largo en tiempo lineal. Se puede hacer en O (n ^ 2) con un esfuerzo de mínimo a medio. Se supone que este algoritmo es bastante "inteligente" para bajarlo a O (n).